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

CREATORWenxuan Xia, Mingyu Yang, Wentao Li, Wei Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.03225

Browse the full library · About the Tower of Babel