Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph
Summary: Analyzes MRNG under cosine similarity, proving greedy search monotonically approaches the query until the true NN and that max out-degree is constant (dataset-size independent), explaining fast search and compact indices. Proposes Hemi-Sphere Centroids Graph (HSCG), an efficient approximate MRNG using hemi-sphere centroids and LSH-based initialization to build cosine-aware graph indices that outperform baselines in search speed and index size. (summarized by gpt-5-mini on Feb 11 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Runwen Qiu (Hong Kong University of Science and Technology)
- 2. Jing Tang (Hong Kong University of Science and Technology)
BibTeX Citation
@inproceedings{qiu_sigmod26,
title = {{Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph}},
author = {Qiu, Runwen and Tang, Jing},
series = {{SIGMOD} '26},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3769786},
url = {https://dl.acm.org/doi/10.1145/3769786},
year = {2026}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4 | The R*-tree: An Efficient and Robust Access Method for Points and Rectangles | 1990 | SIGMOD | 0.001157935 |
| 21 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00056760516 |
| 93 | Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph | 2019 | VLDB | 0.00034701237 |
| 398 | A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search | 2021 | VLDB | 0.00019194947 |
| 1,244 | Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases | 2023 | SIGMOD | 0.00011508159 |
| 1,934 | Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces | 2023 | VLDB | 9.4561907e-05 |
| 5,223 | FARGO: Fast Maximum Inner Product Search via Global Multi-Probing | 2023 | VLDB | 6.3102417e-05 |