Lune

ICDE2024Top-tier venue

Efficient Reverse k Approximate Nearest Neighbor Search Over High-Dimensional Vectors

Yitong Song, Kai Wang, Bin Yao, Zhida Chen, Jiong Xie, Feifei Li

Abstract

Reversekknearest neighbor search(RkNNS)(\mathbf{R}k\mathbf{NNS})plays an important role in various data processing and analysis tasks, seeking to pinpoint data considering the query dataqqamong theirkknearest neighbors. As large models gain popularity, processing high-dimensional vectors has become more and more widespread. However, existingRkNNS\mathbf{R}k\mathbf{NNS}solutions face inefficiency when handling large-scale high-dimensional vectors due to their sensitivity to data dimensions and sizes during index construction or the verification of numerous candidate results in the query phase. Motivated by these challenges and the inherent intricacies of high-dimensional data processing, in this paper, we study an approximate version of theRkNNS\mathbf{R}k\mathbf{NNS}problem(RkANNS)(\mathbf{R}k\mathbf{ANNS})for high-dimensional vectors, aiming to offer efficient and practical solutions. To this end, we propose a new proximity-graph-based index called HAMG, which enables finding the query results withinkkhops fromqq. We also present a user-friendly query algorithm on HAMG that can adaptively adjust the search scope based on the desired query recall of users. To further enhance the query process, two pruning strategies are proposed to reduce the number of candidates requiring verification. Extensive experiments validate that HAMG scales well for data dimensions and sizes, and our query algorithm improves query efficiency by up to two orders of magnitude while maintaining comparable query accuracy against existing approaches.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

its abstract · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. A Topology-Aware Localized Update Strategy for Graph-Based ANN IndexSong Yu, Shengyuan Lin, Shufeng Gong, Yongqing Xie et al.VLDB 2026 · 10 citations

Related papers

  1. ARKGraph: All-Range Approximate K-Nearest-Neighbor GraphChaoji Zuo, Dong DengVLDB 2023 · 18 citations
  2. Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor SearchShuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu et al.VLDB 2025 · 16 citations
  3. GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and ConstructionYuanhang Yu, Dong Wen, Ying Zhang, Lu Qin et al.ICDE 2022 · 28 citations
  4. Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor SearchBinhong Li, Xiao Yan, Shangqi LuSIGMOD 2026 · 1 citation
  5. FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor SearchZekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong et al.SIGMOD 2026
Dusk over the sea between two cliffs drawn in fine vertical lines