Approximate nearest neighbor search (ANNS) in high-dimensional spaces is a
pivotal challenge in the field of machine learning. In recent years,
graph-based methods have emerged as the superior approach to ANNS, establishing
a new state of the art. Although various optimizations for graph-based ANNS
have been introduced, they predominantly rely on heuristic methods that lack
formal theoretical backing. This paper aims to enhance routing within
graph-based ANNS by introducing a method that offers a probabilistic guarantee
when exploring a node's neighbors in the graph. We formulate the problem as
probabilistic routing and develop two baseline strategies by incorporating
locality-sensitive techniques. Subsequently, we introduce PEOs, a novel
approach that efficiently identifies which neighbors in the graph should be
considered for exact distance computation, thus significantly improving
efficiency in practice. Our experiments demonstrate that equipping PEOs can
increase throughput on a commonly utilized graph index (HNSW) by a factor of
1.6 to 2.5, and its efficiency consistently outperforms the leading-edge
routing technique by 1.1 to 1.4 times.

通过引入具有概率保证的方法，该研究旨在增强基于图的最近邻搜索中的路由，提出了 PEOs，一种有效地确定图中应考虑的邻居进行准确距离计算的新方法，实验证明其在常用图索引（HNSW）上可以提高吞吐量 1.6 到 2.5 倍，并且其效率始终比最先进的路由技术提高 1.1 到 1.4 倍。