Sparse Neighborhood Graph-based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis And Optimization

Abstract

Graph-based approaches to approximate nearest neighbor search (ANNS) enable fast, high-recall retrieval on billion-scale vector datasets. Among them, the Sparse Neighborhood Graph (SNG) is widely used due to its strong search performance. However, the lack of theoretical understanding of SNG leads to expensive tuning of the truncation parameter that controls graph sparsification. In this work, we present OPT-SNG, a principled framework for analyzing and optimizing SNG construction. We introduce a martingale-based model of the pruning process that characterizes the stochastic evolution of candidate sets during graph construction. Using this framework, we prove that SNG has a maximum out-degree of \(O(n^\{2/3+\epsilon\})\), where \(\epsilon>0\) is an arbitrarily small constant, and an expected search path length of \(O(log n)\). Building on these insights, we derive a closed-form rule for selecting the optimal truncation parameter \(R\), thereby eliminating the need for costly parameter

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyma2025sparse

Related papers

• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
• High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• Worst-case Performance Of Popular Approximate Nearest Neighbor Search Implementations: Guarantees And Limitations (2023)5.84
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
• A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35
• Revisiting The Index Construction Of Proximity Graph-based Approximate Nearest Neighbor Search (2024)7.16
• Understanding And Generalizing Monotonic Proximity Graphs For Approximate Nearest Neighbor Search (2021)0.00