We present a theoretical and empirical analysis of the adaptive entry point selection for graph-based approximate nearest neighbor search (ANNS). We introduce novel concepts: $b\textit{-monotonic path}$ and $B\textit{-MSNET}$, which better capture an actual graph in practical algorithms than existing concepts like MSNET. We prove that adaptive entry point selection offers better performance upper bound than the fixed central entry point under more general conditions than previous work. Empirically, we validate the method's effectiveness in accuracy, speed, and memory usage across various datasets, especially in challenging scenarios with out-of-distribution data and hard instances. Our comprehensive study provides deeper insights into optimizing entry points for graph-based ANNS for real-world high-dimensional data applications.

我们对于基于图的近似最近邻搜索（ANNS）的自适应入口点选择进行了理论和实证分析。我们引入了新颖的概念：b-单调路径和B-MSNET，其在实际算法中比现有的概念如MSNET更好地捕捉到了真实图形。我们证明了在比以前的工作更一般的条件下，自适应入口点选择提供了比固定中心入口点更好的性能上界。从实证上看，在各种数据集上，尤其是在包含分布之外的数据和难例的挑战情况下，我们在准确性、速度和内存使用方面验证了该方法的有效性。我们的综合研究为优化面向实际高维数据应用的基于图的ANNS的入口点提供了更深入的见解。

基于图的近似最近邻搜索的自适应入口点选择的理论和实证分析