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
- 2. Jing Tang
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 |
|---|---|---|---|---|
| 6 | The R*-tree: An Efficient and Robust Access Method for Points and Rectangles | 1990 | SIGMOD | 0.0016162015 |
| 34 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00076637636 |
| 212 | Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph | 2019 | VLDB | 0.00033913475 |
| 770 | A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search | 2021 | VLDB | 0.00016917602 |
| 2,023 | Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases | 2023 | SIGMOD | 9.7544991e-05 |
| 2,971 | Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces | 2023 | VLDB | 7.7970531e-05 |
| 5,707 | FARGO: Fast Maximum Inner Product Search via Global Multi-Probing | 2023 | VLDB | 5.3611041e-05 |