Theoretical and Empirical Analysis of Adaptive Entry Point Selection for
  Graph-based Approximate Nearest Neighbor Search
Yutaro Oguri Yusuke Matsui
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.