OPT-SNG introduces a martingale model for SNG pruning in ANNS, proves O(n^{2/3+ε}) max out-degree and O(log n) expected path length, and gives a closed-form optimal truncation parameter that yields 5.9× average construction speedup.
Differential equations for random processes and random graphs.The annals of applied probability, pages 1217–1235, 1995
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
OPT-SNG introduces a martingale model for SNG pruning in ANNS, proves O(n^{2/3+ε}) max out-degree and O(log n) expected path length, and gives a closed-form optimal truncation parameter that yields 5.9× average construction speedup.