Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
Summary: OPT-SNG gives SNG a martingale-based theoretical model, proving sparse degree and logarithmic search-path bounds. It derives a closed-form truncation parameter, avoiding tuning sweeps and accelerating construction 5.9× on average (up to 15.4×) without sacrificing recall. (summarized by gpt-5.6-luna on Aug 28 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Xinran Ma (Chinese Academy of Sciences)
- 2. Zhaoqi Zhou (Huawei)
- 3. Chuan Zhou (Chinese Academy of Sciences)
- 4. Zaijiu Shang (Shanghai Institute for Mathematics and Interdisciplinary Sciences)
- 5. Guoliang Li (Tsinghua University)
- 6. Zhiming Ma (Chinese Academy of Sciences)
BibTeX Citation
@article{ma_vldb26,
title = {{Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization}},
author = {Ma, Xinran and Zhou, Zhaoqi and Zhou, Chuan and Shang, Zaijiu and Li, Guoliang and Ma, Zhiming},
journal = {PVLDB},
series = {{VLDB} '26},
volume = {19},
number = {10},
pages = {2817--2830},
doi = {10.14778/3828612.3828634},
url = {https://doi.org/10.14778/3828612.3828634},
year = {2026}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 17 of 17 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next