HRNN: A Hybrid Graph Index for Approximate Reverse k k -Nearest Neighbor Search on High-Dimensional Vectors
Wenxuan Xia, Mingyu Yang, Wentao Li, Wei Wang · 2026
Read HRNN: A Hybrid Graph Index for Approximate Reverse k k -Nearest Neighbor Search on High-Dimensional Vectors by Wenxuan Xia, Mingyu Yang, Wentao Li, Wei Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03225.txt.
Description
Xia, Yang, Li, and Wang speed up reverse nearest neighbor search in high dimensions. A reverse search returns all points that count a query among their own k nearest neighbors. Past methods gather nearby points as candidates, then check each one. Two flaws hurt them. Many nearby points are not true results, and the check needs each point's k-nearest radius, computed online at high cost.
Their index, HRNN, takes a unlike route. Nearby points act as proxies: a query's results are often found through the results of its near points. The index also stores high-grade radii offline, so checks skip costly rebuilds. It joins a navigation graph, a ranked neighbor graph, and reverse-neighbor lists. Tests show throughput up to ten times past methods. The index scales to ten million vectors and supports append-only updates. The work targets fast search in very large vector stores.
Catalog record
| CREATOR | Wenxuan Xia, Mingyu Yang, Wentao Li, Wei Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.03225