Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search

Approximate nearest neighbor (ANN) search in high-dimensional metric spaces is a fundamental problem with many applications. Over the past decade, proximity graph (PG)-based indexes have demonstrated superior empirical performance over alternatives. However, these methods often lack theoretical guarantees regarding the quality of query results, especially in the worst-case scenarios. In this paper, we introduce the 𝛼-convergent graph (𝛼-CG), a new PG structure that employs a new carefully designed edge pruning rule. If the distance between the query point 𝑞 and its exact nearest neighbor 𝑣 * is at most 𝜏 for some constant 𝜏 > 0, our 𝛼-CG finds the exact nearest neighbor in poly-logarithmic time, assuming bounded intrinsic dimensionality for the dataset; otherwise, it can find an ANN in the same time. To enhance scalability, we develop the 𝛼-convergent neighborhood graph (𝛼-CNG), a practical variant that applies the pruning rule locally within each point's neighbors. We also introduce optimizations to reduce the index construction time. Experimental results show that our 𝛼-CNG outperforms existing PGs on real-world datasets. For most datasets, 𝛼-CNG can reduce the number of distance computations and search steps by over 15% and 45%, respectively, when compared with the best-performing baseline.