arXiv CSopen access

HRNN: A Hybrid Graph Index for Approximate Reverse k-Nearest Neighbor Search on High-Dimensional Vectors

HRNN: A Hybrid Graph Index for Approximate Reverse 𝑘-Nearest Neighbor Search on High-Dimensional Vectors Wenxuan Xia

Mingyu Yang

HKUST (GZ) China [email protected]

HKUST (GZ) & HKUST China [email protected]

Wentao Li

Wei Wang

University of Leicester United Kingdom [email protected]

HKUST (GZ) & HKUST China [email protected]

ABSTRACT

1

Reverse 𝑘-nearest neighbor (R𝑘NN) search returns all data points that regard a query vector as one of their 𝑘-nearest neighbors (𝑘NNs). Existing R𝑘NN methods typically follow a filter-andverification framework: vectors near the query vector are first collected as candidates and then verified against their 𝑘NN-radius (i.e., the distance to their 𝑘-th nearest neighbor). However, existing methods face two key limitations in high-dimensional spaces. First, nearby vectors often do not belong to the query’s true R𝑘NN set, resulting in excessive candidate expansion overhead. Second, existing methods compute 𝑘NN-radius online during verification, incurring substantial query-processing cost. To address these limitations, we propose HRNN, a hybrid graph index for approximate R𝑘NN search. (1) Rather than directly treating nearby vectors as R𝑘NN candidates, HRNN uses them as proxy points based on the assumption that a query’s R𝑘NN results can often be discovered through the R𝑘NN results of its nearby vectors. (2) To reduce verification cost, HRNN materializes high-fidelity 𝑘NN-radius offline, eliminating expensive online reconstruction while preserving accuracy. HRNN combines a navigation graph, a ranked KNN graph, and reverse-neighbor lists into a hybrid index that supports efficient proxy retrieval, candidate generation, and 𝑘NN-radius access. We also develop efficient index construction and append-only maintenance algorithms. Extensive experiments show that HRNN consistently outperforms existing methods, achieving up to one order of magnitude higher throughput. Moreover, HRNN scales to datasets containing up to 10 million high-dimensional vectors while supporting efficient dynamic index maintenance.

With the rapid development of large language models (LLMs) and intelligent agents [27, 46], modern data are increasingly represented as high-dimensional vectors, such as text embeddings, image features, and other multi-modal representations [2, 58, 59]. Given a dataset 𝐷 of vectors/data points, the 𝑘-nearest neighbors (𝑘NN) of a data point are the 𝑘 points closest to it, where distance is typically measured using Euclidean distance. Conversely, the reverse 𝑘-nearest neighbors (R𝑘NN) of a query point 𝑞 consist of all data points in 𝐷 that regard 𝑞 as one of their 𝑘-nearest neighbors. Given a dataset 𝐷, the R𝑘NN search problem aims to efficiently retrieve the R𝑘NN set of a query vector 𝑞 from 𝐷. The R𝑘NN set of a query vector 𝑞 naturally reflects its influence over the dataset 𝐷, since each vector in the R𝑘NN set regards 𝑞 as one of its 𝑘-nearest neighbors. Consequently, R𝑘NN search has been widely used in applications that require influence analysis and reverse relationship discovery. For example, in spatial analytics, R𝑘NN search can identify attractive facility locations by finding sites that appear among the 𝑘-nearest neighbors of a large number of customers [7]. In retrieval-augmented generation (RAG) systems, R𝑘NN search can help identify influential knowledge chunks that are frequently referenced by many queries. More broadly, R𝑘NN search has been extensively studied in machine learning tasks that rely on reverse influence relationships among data points, including density-based clustering [5, 10, 20], outlier detection [4, 19, 37], and class-imbalance sampling [38, 60]. To process the R𝑘NN search for a query 𝑞, an intuitive approach is to first compute the 𝑘NN set of every point 𝑜 in the dataset 𝐷 and obtain its 𝑘NN-radius, i.e., the distance between 𝑜 and its 𝑘-th nearest neighbor. Then, by definition, if the distance between 𝑞 and point 𝑜 ∈ 𝐷 does not exceed the 𝑘NN radius of 𝑜, 𝑜 is identified as an R𝑘NN of 𝑞. However, this intuitive approach becomes prohibitively expensive when the dataset is large or the vector dimensionality is high. Although prior studies [7, 40] have explored spatial indexes such as R-trees to accelerate R𝑘NN search, exact R𝑘NN retrieval in high-dimensional vector spaces remains challenging. Thus, this paper focuses on approximate R𝑘NN (i.e., AR𝑘NN) search.

PVLDB Reference Format: Wenxuan Xia, Mingyu Yang, Wentao Li, and Wei Wang. HRNN: A Hybrid Graph Index for Approximate Reverse 𝑘-Nearest Neighbor Search on High-Dimensional Vectors. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/gegeji/hrnn. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX

INTRODUCTION

Existing Solutions. Existing methods for AR𝑘NN search generally follow a filter-and-verification framework. They first retrieve a superset of potential R𝑘NN results for a query 𝑞 as candidates, and then verify each candidate using a process similar to the intuitive

Table 1: Comparison between HRNN and existing R𝑘NN methods.

RkNN Baseline Search Space ( NNs or k-hop expansion)

Scanned False Positives

Figure 1: Illustration of the inefficiency of existing methods. The radius of the circles centered at points (e.g., 𝑝 1 and 𝑝 2 ) in the dataset 𝐷 denotes their 𝑘NN-radius. Given a query vector 𝑞, the goal is to retrieve its R𝑘NN results (𝑝 1 and 𝑝 2 in this example, as we set 𝑘 = 1). Existing methods typically explore nearby neighbors, such as through top-𝑘 ′ (𝑘 ′ >> 𝑘) nearest-neighbor search or 𝑘-hop graph expansion, and then verify whether the retrieved candidates are true R𝑘NN results. However, to reach 𝑝 2 , which has a large 𝑘NN-radius due to its sparse neighborhood, these methods must traverse a large search region and examine many false positive candidates (gray points), resulting in substantial unnecessary computation.

HRNN (Ours)

HAMG

RDT

SFT

Filter (Candidate Generation)

Reverseneighbor lists of proxies

𝑘-hop graph Incremental traversal 𝑘NN search

Verification

Online Online Online Prematerialized computation computation computation 𝑘NN-radius

One-shot 𝑘NN search

As a result, candidate verification introduces substantial computational overhead and becomes a major bottleneck in existing R𝑘NN methods, as confirmed by our empirical studies. Our Solution. To address the limitations of existing methods, we propose HRNN, a Hybrid graph index for approximate Reverse 𝑘-Nearest Neighbor search. (1) To overcome the mismatch between R𝑘NN results and nearby neighbors, rather than assuming that a query’s nearby neighbors directly contain its R𝑘NN results, we make a different assumption: a query’s R𝑘NN results can often be discovered through the R𝑘NN results of its nearby neighbors. Based on this assumption, HRNN first retrieves the query’s nearby neighbors (i.e., 𝑘NNs) as proxy points and then leverages their R𝑘NN results to recover the query’s R𝑘NN results. To support this process, each point maintains a reverse-neighbor list that records the points in 𝐷 whose nearest-neighbor lists contain it, enabling efficient retrieval of its R𝑘NN results for arbitrary 𝑘 when used as a proxy. This design avoids excessive neighborhood expansion while maintaining high retrieval accuracy. (2) To address the high verification cost of existing methods, HRNN eliminates the expensive online computation of 𝑘NN-radius during query processing. Instead, it materializes 𝑘NN-radius information offline, enabling efficient candidate verification at query time. Achieving these goals is non-trivial, as the index must simultaneously support 𝑘NN retrieval for query vectors, reverse-neighbor-list access for proxy points, and fast 𝑘NN-radius lookup for arbitrary values of 𝑘. To this end, HRNN integrates two complementary graph structures. First, it employs a navigation graph, such as HNSW [33], to retrieve the query’s nearest neighbors as proxy points. Second, it maintains a ranked KNN graph [12] that stores nearest-neighbor relationships among data points. This graph provides direct access to pre-materialized 𝑘NN-radius for verification and serves as the basis for constructing reverse-neighbor lists, which enable efficient retrieval of proxy points’ R𝑘NN results for candidate generation. By tightly integrating a navigation graph, a ranked KNN graph, and reverse-neighbor lists into a unified index, HRNN enables efficient R𝑘NN query processing. We further develop efficient index construction and insertion-only maintenance algorithms. A comparison between HRNN and existing methods is in Table 1.

approach described above. Early methods mainly rely on spatial partitioning [42, 43] or precomputed distance bounds [1] to prune unpromising vectors from the dataset. Yet, these approaches suffer from high preprocessing and indexing costs in high-dimensional spaces due to the curse of dimensionality [21]. More recent methods, including SFT [39], RDT [6], and the state-of-the-art HAMG [41], are based on the assumption that the R𝑘NNs of a query vector often overlap significantly with its nearby neighbors. Thus, these methods first retrieve nearby neighbors as candidates, such as the top-𝑘 ′ nearest neighbors of the query vector in SFT [39] and RDT [6], where 𝑘 ′ >> 𝑘, or the 𝑘-hop neighbors in graphbased methods such as HAMG [41]. They then verify whether each candidate belongs to the R𝑘NN set of the query by comparing the query distance against the candidate’s 𝑘NN-radius. Limitations. Although recent methods achieve good performance by considering the properties of high-dimensional spaces, they still suffer from inherent limitations that restrict their efficiency. Limitation 1: The mismatch between R𝑘NN and nearby neighbors. Existing methods need to examine a large number of nearby neighbors to achieve high recall, because true R𝑘NN results can be far away from the query vector in the embedding space (see Fig. 1 and Fig. 4). For example, a point 𝑜 ∈ 𝐷 may still regard query vector 𝑞 as one of its 𝑘-nearest neighbors if 𝑜 lies in a sparse region and therefore has a large 𝑘NN-radius. As a result, the query must search a large neighborhood region before reaching 𝑜, leading to excessive candidate expansion and unnecessary verification cost. This mismatch between R𝑘NN results and nearby neighbors fundamentally limits the efficiency of existing methods. Limitation 2: High verification cost. After generating candidate points, existing methods verify whether a candidate 𝑜 belongs to the final R𝑘NN result by comparing the distance between 𝑞 and 𝑜 against the 𝑘NN-radius of 𝑜. Specifically, if 𝛿 (𝑞, 𝑜) is no larger than the 𝑘NN-radius of 𝑜, then 𝑞 is regarded as one of the 𝑘-nearest neighbors of 𝑜, and thus 𝑜 is an R𝑘NN of 𝑞. Yet, the 𝑘NN-radius of each candidate is typically computed online during query time [6, 41, 54], as precomputing and storing these distances for all 𝑘 values incurs prohibitive preprocessing costs or requires rebuilding the index.

Contributions. We summarize our main contributions as follows. Problem analysis (§3). We identify two key shortcomings of existing methods for high-dimensional AR𝑘NN search. First, true R𝑘NN results can be far away from the query vector in the embedding space, and thus the mismatch between R𝑘NN results and nearby neighbors leads to excessive false positive candidates and unnecessary computation. Second, the 𝑘NN-radius of each candidate is computed online, which incurs huge overhead during the verification stage. 2

Table 2: Notation summary. Notation

Description

𝐺 HNSW 𝐺 KNN 𝐺 KNN [𝑜 ] R[𝑜 ] 𝑟𝑘 (𝑜 ) 𝑘 K Θ 𝑚 Θ𝑢 𝑚𝑢

HNSW navigation graph Ranked KNN graph Ranked KNN list of 𝑜 , sorted by distance Reverse-neighbor list of 𝑜 𝑘 NN radius (distance to the 𝑘 -th nearest neighbor) of 𝑜 Target parameter for 𝑘 NN or R𝑘 NN search Number of stored neighbors per vertex in 𝐺 KNN Rank threshold for reverse candidate generation Number of proxy vectors retrieved from 𝐺 HNSW Rank threshold used during insertion maintenance Number of update proxies used during insertion maintenance

(a)

spaces, existing methods typically trade accuracy for efficiency by returning approximate results. We therefore formally define the problem of approximate R𝑘NN (AR𝑘NN) search as follows. Definition 2.3 (Approximate Reverse 𝑘-Nearest Neighbor (AR𝑘NN) Search). Given a dataset 𝐷, a query vector 𝑞, and an integer 𝑘, an AR𝑘NN search returns a set 𝐴ˆ𝑘 (𝑞) ⊆ 𝐷 as an approximation to the exact R𝑘NN result set 𝐴𝑘 (𝑞). Its accuracy is evaluated against 𝐴𝑘 (𝑞) rather than by an 𝜖-relaxed membership predicate.

Hybrid index design (§4). We propose HRNN, a hybrid graph index for efficient AR𝑘NN search. HRNN integrates a navigation graph, a ranked KNN graph, and reverse-neighbor lists derived from the ranked KNN graph. The navigation graph is used to efficiently retrieve nearby proxy points, while the reverse-neighbor lists are used to recover the R𝑘NN candidates of the query vector. In addition, the ranked KNN graph materializes 𝑘NN-radius information for arbitrary values of 𝑘, enabling efficient candidate verification without expensive online 𝑘NN-radius computation. Index construction and maintenance (§4). We develop efficient algorithms for HRNN index construction and maintenance. Specifically, we use the navigation graph as initialization seeds to improve the construction quality of the ranked KNN graph. We further propose efficient methods to construct reverse-neighbor lists and support insertion-only index maintenance under dynamic updates. Extensive experimental studies (§5). Extensive experiments on four real-world datasets show that HRNN improves the recallthroughput trade-off over strong R𝑘NN baselines by up to one order of magnitude. Additional ablation, varying-𝑘, and scalability experiments further validate the effectiveness of our HRNN.

2

Following [41], we use Recall@𝑘 to evaluate the accuracy of AR𝑘NN results against the exact R𝑘NN ground truth. Definition 2.4 (Recall@𝑘). For a query 𝑞, let 𝐴𝑘 (𝑞) denote the exact R𝑘NN result set and let 𝐴ˆ𝑘 (𝑞) denote the approximate result set. The per-query Recall@𝑘 is defined as |𝐴𝑘 (𝑞)∩𝐴ˆ𝑘 (𝑞) | ⎧ ⎪ , |𝐴𝑘 (𝑞)| > 0, ⎪ ⎨ |𝐴𝑘 (𝑞) | ⎪ Recall@𝑘 (𝑞) = 1, |𝐴𝑘 (𝑞)| = 0 and |𝐴ˆ𝑘 (𝑞)| = 0, ⎪ ⎪ ⎪ 0, ˆ |𝐴 𝑘 (𝑞)| = 0 and |𝐴𝑘 (𝑞)| > 0. ⎩ For a query workload 𝑄, Recall@𝑘 is computed as the average of Recall@𝑘 (𝑞) over all 𝑞 ∈ 𝑄. Example 2.5. Fig. 2 shows 𝑘NN and R𝑘NN search. Let 𝑥 1, . . . , 𝑥 4 be data points and 𝑞 the query, with 𝑘 = 1. In Fig. 2(a), the nearest neighbor of 𝑞 is 𝑥 4 , and the (radius of the) circle centered at 𝑞 denotes its 𝑘NN-radius. In Fig. 2(b), the circles centered at 𝑥 1, . . . , 𝑥 4 indicate their 𝑘NN-radius. Since 𝑞 lies within the 𝑘NN-radius of 𝑥 3 and 𝑥 4 but outside those of 𝑥 1 and 𝑥 2 , the R𝑘NN result set of 𝑞 is {𝑥 3, 𝑥 4 }.

PRELIMINARY

We first formulate the approximate R𝑘NN search problem, and then introduce the graph-based index that supports 𝑘NN retrieval.

2.1

(b)

Figure 2: Illustrative examples of 𝑘NN and R𝑘NN search.

2.2

Graph-Based 𝑘NN Search

We briefly introduce graph-based methods for high-dimensional 𝑘NN search, which serve as the foundation of the studied AR𝑘NN search problem. Among existing high-dimensional 𝑘NN methods, graph-based approaches [8, 12–14, 17, 18, 22, 23, 28, 30, 32, 33, 36, 47, 49, 50, 61] are particularly popular due to their state-of-theart performance. These methods model the points in dataset 𝐷 as vertices in a graph and connect nearby vertices through directed or undirected edges. As a result, 𝑘NN search for a query vector 𝑞 becomes a graph traversal process over the constructed index.

Problem Definition

We first introduce the definitions of 𝑘NN and R𝑘NN, and then formally define the studied problem. Table 2 summarizes the commonly used notations in this paper. Definition 2.1 (𝑘-Nearest Neighbor (𝑘NN)). Given a dataset 𝐷 of points in Euclidean space R𝑑 , a 𝑑-dimensional query vector 𝑞, and an integer 𝑘, the 𝑘NN set 𝑁𝑘 (𝑞) of 𝑞 is a subset of 𝐷 such that |𝑁𝑘 (𝑞)| = 𝑘 and ∀𝑣 ∈ 𝑁𝑘 (𝑞), ∀𝑥 ∈ 𝐷 \ 𝑁𝑘 (𝑞), 𝛿 (𝑣, 𝑞) ≤ 𝛿 (𝑥, 𝑞). where 𝛿 (𝑣, 𝑞) denotes the Euclidean distance between 𝑣 and 𝑞.

Ranked KNN Graph. We first introduce the ranked KNN graph, where K is a user-defined parameter chosen to be sufficiently large to support 𝑘NN search for arbitrary 𝑘 ≤ K.

Note that 𝑞 may not belong to 𝐷. For each point 𝑜 ∈ 𝐷, let 𝑁𝑘 (𝑜) denote its 𝑘NN in 𝐷, and let its 𝑘NN-radius be defined as 𝑟𝑘 (𝑜) = 𝛿 (𝑜, 𝑣), where 𝑣 ∈ 𝑁𝑘 (𝑜) is the 𝑘-th nearest neighbor of 𝑜.

Definition 2.6 (Ranked KNN Graph). Given a dataset 𝐷 ⊂ R𝑑 and an integer K, the ranked KNN graph 𝐺 KNN = (𝑉 , 𝐸) is a directed graph with vertex set 𝑉 = 𝐷. Each vertex 𝑜 ∈ 𝑉 stores an ordered KNN list of its K nearest neighbors and their distances: 𝐺 KNN [𝑜] = {(𝑣 1, 𝛿 (𝑜, 𝑣 1 )), . . . , (𝑣 K, 𝛿 (𝑜, 𝑣 K ))}, where 𝛿 (𝑜, 𝑣 1 ) ≤ . . . ≤ 𝛿 (𝑜, 𝑣 K ). A directed edge 𝑜 → 𝑣 𝑗 exists if 𝑣 𝑗 is the 𝑗-th nearest neighbor of 𝑜, i.e., 𝐺 KNN [𝑜, 𝑗] = 𝑣 𝑗 . For simplicity, we write 𝐺 KNN [𝑜, 𝑗] = 𝑣 𝑗 , although the actual entry is (𝑣 𝑗 , 𝛿 (𝑜, 𝑣 𝑗 )).

Definition 2.2 (Reverse 𝑘-Nearest Neighbor (R𝑘NN)). Given a dataset 𝐷 ⊆ R𝑑 , a 𝑑-dimensional query vector 𝑞, and an integer 𝑘, the R𝑘NN set of 𝑞 is defined as 𝐴𝑘 (𝑞) = {𝑜 ∈ 𝐷 | 𝛿 (𝑞, 𝑜) ≤ 𝑟𝑘 (𝑜)}. The R𝑘NN set 𝐴𝑘 (𝑞) contains all points 𝑜 ∈ 𝐷 that regard 𝑞 as one of their 𝑘 nearest neighbors. Equivalently, the distance between 𝑞 and 𝑜 is no larger than the 𝑘NN-radius of point 𝑜. Since exact R𝑘NN search is computationally expensive in high-dimensional 3

Algorithm 1: Ranked KNN Graph Construction

Algorithm 2: Graph-Search(𝐺, 𝑞, 𝑘, 𝑒𝑝, 𝑒 𝑓 )

Input: Dataset 𝐷, integer K Output: Ranked KNN graph 𝐺 KNN 1 Initialize 𝐺 KNN [𝑜 ] with K random points for eacn 𝑜 ∈ 𝐷; 2 repeat 3 Create R[𝑜 ] ← {𝑥 | 𝑜 ∈ 𝐺 KNN [𝑥 ] } for each 𝑜 ∈ 𝐷; 4 for each𝑜 ∈ 𝐷 do 𝑁 [𝑜 ] ← 𝐺 KNN [𝑜 ] ∪ R[𝑜 ]; 5 for each 𝑜 ∈ 𝐷 do 6 for each neighbor pair (𝑢, 𝑣) in 𝑁 [𝑜 ] do 7 Compute 𝑑 = 𝛿 (𝑢, 𝑣); 8 Insert (𝑣, 𝑑 ) into 𝐺 KNN [𝑢 ] if improved; 9 Insert (𝑢, 𝑑 ) into 𝐺 KNN [𝑣 ] if improved;

Input: Graph 𝐺, query vector 𝑞, target number of results 𝑘, entry point 𝑒𝑝, beam width 𝑒 𝑓 Output: Candidate set 𝑊 [𝑞 ] of size 𝑘 1 Initialize min-heap 𝑄 ← {𝑒𝑝 } ordered by 𝛿 (𝑞, ·); 2 Initialize max-heap 𝑊 [𝑞 ] ← {𝑒𝑝 } ordered by 𝛿 (𝑞, ·); 3 Mark 𝑒𝑝 as visited; 4 while 𝑄 ≠ ∅ do 5 Extract the closest vertex 𝑣 from 𝑄; 6 Let 𝑢 be the farthest vertex in 𝑊 [𝑞 ]; 7 if𝛿 (𝑞, 𝑣) > 𝛿 (𝑞, 𝑢 ) then break; 8 for each unvisited neighbor 𝑜 ∈ 𝐺 [𝑣 ] do 9 Mark 𝑜 as visited; 10 if |𝑊 [𝑞 ] | < 𝑘 or 𝛿 (𝑞, 𝑜 ) < 𝛿 (𝑞, 𝑢 ) then 11 Insert 𝑜 into both 𝑄 and 𝑊 [𝑞 ]; 12 if |𝑊 [𝑞 ] | > 𝑘 then 13 Remove the farthest vertex from 𝑊 [𝑞 ];

10

until no neighbor list changes;

The ranked 𝐺 KNN captures nearest-neighbor relationships from the perspective of each point in 𝐷. Transposing these relationships yields reverse-neighbor lists, which record, for each vector, the points that regard it as one of their top-K nearest neighbors. Consequently, the R𝑘NN results of any dataset vector can be obtained directly from its reverse-neighbor list for any 𝑘 ≤ K.

14 15

16

Definition 2.7 (Reverse-Neighbor List). Given a ranked 𝐺 KNN , the reverse-neighbor list of a vector 𝑜 ∈ 𝐷, denoted by R[𝑜], is defined as R[𝑜] = {(𝑣, 𝑗) | 𝑣 ∈ 𝐷, 𝐺 KNN [𝑣, 𝑗] = 𝑜, 1 ≤ 𝑗 ≤ K}, where (𝑣, 𝑗) indicates that 𝑜 is the 𝑗-th nearest neighbor of 𝑣.

if |𝑄 | > 𝑒 𝑓 then Remove the farthest vertex from 𝑄; return 𝑊 [𝑞 ];

appears in all layers 𝐺 (0) , . . . , 𝐺 (𝜆 (𝑜 ) ) . At each layer ℓ ≤ 𝜆(𝑜), point 𝑜 maintains a bounded sized neighbor list 𝐺 (ℓ ) [𝑜] = {𝑣 1, . . . , 𝑣 𝑀 }, where each 𝑣𝑖 ∈ 𝑉 (ℓ ) is selected using proximity-based pruning heuristics. A directed edge 𝑜 → 𝑣𝑖 exists in layer 𝐺 (ℓ ) if 𝑣𝑖 ∈ 𝐺 (ℓ ) [𝑜]. Search on the HNSW graph. Given a query 𝑞, an HNSW graph 𝐺 HNSW , the target result size 𝑘, and a beam width 𝑒 𝑓 , search on the HNSW index proceeds from the top layer to the bottom layer. Starting from the global entry point in the top layer, the algorithm first performs greedy search on each upper layer with beam width 𝑒 𝑓 = 1, so that only the closest candidate is retained and used as the entry point for the next lower layer. After reaching the bottom layer 𝐺 (0) , the algorithm performs beam search with a larger beam width 𝑒 𝑓 > 1 to retrieve the final 𝑘NN result for the query vector 𝑞. The search within each layer 𝐺 (ℓ ) follows Algorithm 2. Given the current entry point 𝑒𝑝, the algorithm initializes a candidate heap 𝑄 and a result heap 𝑊 [𝑞] with 𝑒𝑝 (Lines 1–2), and marks it as visited (Line 3). It then repeatedly extracts the closest vertex 𝑣 from 𝑄 (Line 5) and compares it with the farthest vertex 𝑢 in 𝑊 [𝑞] (Line 6). If 𝑣 is farther from 𝑞 than 𝑢, the search stops because no remaining candidate can improve the current result (Line 7). Otherwise, the algorithm scans each unvisited neighbor 𝑜 ∈ 𝐺 (ℓ ) [𝑣] (Line 8), marks it as visited (Line 9), and inserts it into both 𝑄 and 𝑊 [𝑞]. if 𝑊 [𝑞] has fewer than 𝑘 vertices or 𝑜 is closer to 𝑞 than the current farthest candidate (Lines 10–11). If 𝑊 [𝑞] or 𝑄 exceeds their size limits, the farthest vertex is removed (Line 12–15). The search returns 𝑊 [𝑞] as the result (Line 16).

Index construction. Exact construction of ranked KNN graph requires 𝑂 (|𝐷 | 2 ) distance computations, since the K-nearest neighbors must be identified for every point in 𝐷. To improve efficiency, NNDescent [12] iteratively refines the KNN list of each point based on the neighbors of its current neighbors. Algorithm 1 shows how to create the ranked KNN graph using NNDescent. It first initializes the neighbor list 𝐺 KNN [𝑜] of each point 𝑜 ∈ 𝐷 with K random points (Line 1). During each iteration, it constructs a reverseneighbor list R[𝑜] for every point 𝑜, which contains all points that currently include 𝑜 in their neighbor lists (Line 3). The forward and reverse neighbor lists are then merged to form the neighbor set 𝑁 [𝑜] (Line 4). For each neighbor pair (𝑢, 𝑣) in 𝑁 [𝑜] (Lines 5–6), the algorithm computes their distance 𝛿 (𝑢, 𝑣) and attempts to insert (𝑣, 𝑑) into 𝐺 KNN [𝑢] and (𝑢, 𝑑) into 𝐺 KNN [𝑣] if the new neighbor improves the current ranked neighbor list (Lines 7–9). Here, we say that (𝑣, 𝑑) updates 𝐺 KNN [𝑢] if the distance 𝑑 = 𝛿 (𝑢, 𝑣) is smaller than the distance between 𝑢 and at least one neighbor currently stored in 𝐺 KNN [𝑢]. The refinement process repeats until no neighbor list changes further (Line 10). For simplicity, we omit several optimizations, such as neighbor sampling and lazy updates. Navigation Graph. Ranked KNN graphs mainly connect each point to its local neighbors and therefore lack long-range edges. As a result, greedy graph traversal from a random entry point can easily become trapped in local optima [18]. To address this limitation, navigation graphs [14], such as the Hierarchical Navigable Small World (HNSW) graph [33], have been proposed.

Example 2.9. Fig. 3(a) illustrates an HNSW graph with three layers, where 𝐺 (2) is the top layer and 𝐺 (0) is the bottom layer. Given a query vector 𝑞, the top-down routing phase starts from the global entry point 𝑒𝑝 = 𝑥 4 and performs greedy search (𝑒 𝑓 = 1) on each layer. The search progressively descends through the hierarchy until reaching the bottom layer, where 𝑥 7 is identified as the entry point. Fig. 3(b) illustrates the bottom-layer beam search (𝑒 𝑓 = 2). Starting from 𝑥 7 , the search visits 𝑥 5 and inserts 𝑥 2 and 𝑥 9 into the candidate queue. Since 𝛿 (𝑞, 𝑥 2 ) < 𝛿 (𝑞, 𝑥 9 ), 𝑥 2 is expanded

Definition 2.8 (HNSW Graph). Given a dataset 𝐷 ⊂ R𝑑 , an HNSW graph is an 𝐿-layer directed proximity graph 𝐺 HNSW = {𝐺 (0) , 𝐺 (1) , . . . , 𝐺 (𝐿) }, where each layer 𝐺 (ℓ ) = (𝑉 (ℓ ) , 𝐸 (ℓ ) ) is defined over a subset 𝑉 (ℓ ) ⊆ 𝐷, satisfying 𝑉 (𝐿) ⊆ 𝑉 (𝐿−1) ⊆ · · · ⊆ 𝑉 (0) = 𝐷. Each point 𝑜 ∈ 𝐷 is assigned a maximum level 𝜆(𝑜) and 4

GIST (𝑑 =960)

SIFT (𝑑 =128)

MSMARCO (𝑑 =1024)

CDF

1 0.5 0 100

101

102

105

106

(a) Total query latency (ms)

H

RN

N

0.14 0.38

550 3542

347 1277 H

AM G

103 101 10 −1

322 1186

MSMARCO

SF T

N

2.1 4.1

120 471 RN H

32 127

AM G H

SF T

RD T

103 102 101 100

We summarize existing methods for R𝑘NN search in Section 3.1, and then analyze their two limitations in Section 3.2. This analysis motivates our method presented in Section 4. For simplicity, we use the term R𝑘NN search to refer to approximate R𝑘NN search throughout the remainder of the paper unless otherwise specified.

18 57

SIFT

PROBLEM ANALYSIS

RD T

first, followed by 𝑥 9 , which discovers 𝑥 1 . The final 2NN result is 𝑊 [𝑞] = 𝑥 1, 𝑥 2 (shaded in purple).

3.1

104

Figure 4: The cumulative distribution function (CDF) of the ranks of points in the R𝑘NN result sets of query vectors. A higher rank indicates that more nearby neighbors must be explored before the exact R𝑘NN (𝑘 = 10) results can be retrieved.

(a) (b) Figure 3: Illustration of an HNSW graph and the graph search process.

3

103

Rank of farthest R𝑘 NN groundtruth result among 𝑞 ’s neighbors

(b) Verification cost (𝜇 s/cand.)

Figure 5: Comparison of query performance for approximate R𝑘NN search with 𝑘 = 10 at Recall@10 = 0.99. (a) shows the total query latency of HRNN and the baselines (SFT, RDT, and HAMG). (b) reports the per-candidate verification cost of HRNN and the baselines.

Existing Solutions

The main challenge in answering the R𝑘NN search problem lies in two aspects. First, unlike 𝑘NN search, where the result vectors are directly close to the query vector 𝑞, the vectors in the R𝑘NN set do not necessarily have explicit proximity relationships with 𝑞. Specifically, R𝑘NN search is defined from the perspective of dataset points 𝑜 ∈ 𝐷: we need to determine whether 𝑞 belongs to the 𝑘NN set of points 𝑜 by checking the 𝑘NN-radius of 𝑜. Second, unlike 𝑘NN search, which always returns exactly 𝑘 vectors, the number of reverse 𝑘NN results for a query vector is unknown in advance. To process the R𝑘NN search problem for a query vector 𝑞 over dataset 𝐷, an intuitive approach is to directly follow the definition of R𝑘NN. Specifically, the algorithm scans all points 𝑜 ∈ 𝐷 and checks whether the distance 𝛿 (𝑞, 𝑜) is no larger than the 𝑘NN-radius 𝑟𝑘 (𝑜) of 𝑜, where 𝑟𝑘 (𝑜) is defined as the distance from 𝑜 to its 𝑘-th nearest neighbor. If so, 𝑜 is included in the R𝑘NN set of 𝑞. However, this approach is computationally expensive for large-scale datasets. Filter-and-Verification Framework. To improve efficiency, existing methods typically adopt a filter-and-verification framework. Instead of examining all points in 𝐷, these methods first reduce the search space to a candidate set 𝐶 ⊆ 𝐷, and then verify whether each candidate point belongs to the R𝑘NN result set of the query vector 𝑞. To obtain a compact candidate set 𝐶, existing methods commonly assume that data points close to 𝑞 are more likely to regard 𝑞 as one of their 𝑘 nearest neighbors, and thus are more likely to belong to the R𝑘NN result set of 𝑞. Based on this assumption, methods such as SFT [39] and RDT [6] first perform nearest-neighbor search and then examine nearby neighbors as candidates until a stopping condition is satisfied. The State-of-the-Art. More recently, HAMG [41] was proposed following the same intuition. A key insight of HAMG is that, on the Monotonic Relative Neighborhood (MRN) graph [3, 8, 12– 14, 18, 22, 23, 28, 30, 32, 33, 36, 45, 47, 49, 50, 53], the R𝑘NN results of a query vector 𝑞 are guaranteed to lie within the 𝑘-hop neighborhood of 𝑞. Based on this property, HAMG treats these nearby graph neighbors as the candidate set 𝐶. Specifically, HAMG adopts the hierarchical structure of the (HNSW) graph in Definition 2.8,

while modifying the bottom layer 𝐺 (0) to better approximate the MRN graph structure. Using this adapted (HNSW) graph, HAMG retrieves the 𝑘-hop neighbors of 𝑞 as candidates and then verifies whether 𝛿 (𝑞, 𝑜) ≤ 𝑟𝑘 (𝑜) for each candidate 𝑜 ∈ 𝐶 to determine if 𝑜 belongs to the R𝑘NN set of 𝑞. More details can be found in [41].

3.2

Limitation Analysis

Existing methods avoid scanning the entire dataset 𝐷 to retrieve the R𝑘NN results of a query vector 𝑞. Yet, they still suffer from two major limitations that reduce their efficiency on large datasets. Limitation 1: The mismatch between R𝑘NN and nearby neighbors. Existing methods rely on the assumption that nearby neighbors of 𝑞 (e.g., nearest neighbors in SFT and RDT, or graph neighbors within 𝑘 hops in HAMG) contain all R𝑘NN results. Although this assumption generally holds, it can still lead to high query latency in practice. As illustrated in the introduction (Fig. 1), when an object 𝑜 ∈ 𝐷 has a large 𝑘NN-radius, the query vector 𝑞 may still belong to the 𝑘NN set of 𝑜 even if 𝑜 is far away from 𝑞. Consequently, the search algorithm must traverse a large number of nearby neighbors before reaching 𝑜. Even for the state-of-the-art HAMG, the number of 𝑘-hop graph neighbors can become extremely large due to the graph expansion effect. As a result, a substantial amount of computation spent exploring nearby neighbors is unnecessary. To further validate this limitation, we report the statistics in Fig. 4. We evaluate three datasets, GIST, SIFT, and MSMARCO, with dimensions 960, 128, and 1024, respectively, and set 𝑘 = 10 for R𝑘NN search. For each query 𝑞, we compute its exact R𝑘NN result set. For every object in the result set, we measure its rank in the nearest-neighbor ordering of 𝑞, where the closest neighbor has rank 1 and the farthest point has rank |𝐷 |. We then compute the cumulative distribution function (CDF) of these rankings. The results show that all three datasets require exploring a large number of nearby neighbors to retrieve all R𝑘NN results. For example, on SIFT, more than 50% of queries require scanning over 103 nearby neighbors to retrieve all R𝑘NN results. More critically, some queries 5

𝑚 =1

𝑚 =10

Θ =500

CDF

𝑚 =20

1

102

0.5 104

Proxy rank 𝜌𝑚 (𝑞, 𝑥 )

(a) SIFT (𝑑 =128)

106

0 100

102

104

Proxy rank 𝜌𝑚 (𝑞, 𝑥 )

106

(b) MSMARCO (𝑑 =1024)

Figure 6: To validate our assumption, we evaluate the proxy ranks of exact R𝑘NN results on the SIFT and MSMARCO datasets. For each query vector 𝑞, its top-𝑚 nearest neighbors are used as proxies (𝑚 ∈ {1, 5, 10, 20}). Consider an exact R𝑘NN result 𝑥 (𝑘 = 10) of 𝑞. We define the proxy rank of 𝑥 as the smallest rank position of any proxy of 𝑞 in 𝑥’s ranked KNN list. By Definition 2.7, if a proxy appears at rank 𝑟 in 𝑥’s ranked KNN list, then 𝑥 appears in the proxy’s reverse-neighbor list and can be discovered after scanning its reverse-neighbor list. Therefore, a small proxy rank of 𝑟 indicates that 𝑥 can be recovered through at least one proxy after examining only the first few entries of its reverse-neighbor list. The results show that proxy ranks are generally small and decrease as 𝑚 increases. In particular, about 50% of the R𝑘NN results have proxy ranks below 50, indicating that most results can be recovered by scanning only a short prefix of the proxies’ reverse-neighbor lists.

design avoids excessive neighborhood expansion while keeping high recall. Idea 2. To address Limitation 2, we eliminate the expensive online computation of 𝑘NN-radius during verification. Recall that the 𝑘NNradius of a vector 𝑜 ∈ 𝐷 is simply the distance between 𝑜 and its 𝑘-th nearest neighbor. Thus, if we materialize a ranked neighbor list for each vector and store the corresponding distances in ascending order, the 𝑘NN-radius for any value of 𝑘 can be retrieved directly through a lookup. This transforms verification from an expensive online search into a lightweight index-access operation.

THE PROPOSED METHOD

Index Design. To realize the above intuitions, the index must support three operations: (1) efficiently retrieving nearby neighbors of a query vector as proxies, (2) obtaining the reverse-neighbor lists of proxy points to generate R𝑘NN candidates for the query, and (3) maintaining ranked neighbor lists for all points in the dataset so that 𝑘NN-radius can be accessed efficiently during verification. Designing a single index that satisfies all these requirements is non-trivial. For example, the HNSW graph is highly effective for nearest-neighbor retrieval but does not maintain ranked neighbor lists. In contrast, a ranked KNN graph provides ranked neighbor information but is inefficient for query-time nearest-neighbor search. Moreover, neither structure directly supports efficient access to the R𝑘NN sets of data vectors. To address these challenges, we propose HRNN, a hybrid index that integrates an HNSW graph, a ranked KNN graph, and reverse-neighbor lists.

We first introduce the proposed index structure in Section 4.1, followed by the query processing algorithm in Section 4.2. Then, Section 4.3 describes the index construction procedure, and Section 4.4 presents the append-only index maintenance method.

4.1

0.5 0 100

Limitation 2: High Verification Cost. The first limitation implies that existing R𝑘NN methods often explore a large number of unnecessary neighbors during the filter stage, producing a candidate set 𝐶 that is substantially larger than the true R𝑘NN result set. Then, for each candidate vector 𝑜 ∈ 𝐶, the algorithm must determine whether 𝛿 (𝑜, 𝑞) ≤ 𝑟𝑘 (𝑜). If the condition does not hold, then 𝑞 is not among the 𝑘 nearest neighbors of 𝑜, and 𝑜 is discarded; otherwise, 𝑜 is reported as an R𝑘NN result. Consequently, efficient computation of the 𝑘NN-radius 𝑟𝑘 (𝑜) of 𝑜 is critical to R𝑘NN search performance. Obtaining this value requires issuing a 𝑘NN query centered at 𝑜, as precomputing 𝑘NN-radius and supporting queries for arbitrary 𝑘 values necessitate either prohibitive preprocessing cost or even complete index reconstruction in existing indexes [6, 39, 41, 54]. Besides, since the candidate set 𝐶 is not known in advance and can be very large in practice, existing methods incur substantial overhead by computing 𝑘NN-radius online during query processing. To quantify this limitation, we conduct experiments on the realworld SIFT and MSMARCO datasets. We compare the runtime of approximate R𝑘NN search across HRNN and the baseline methods (SFT, RDT, and HAMG), with the results reported in Fig. 5. As shown in Fig. 5(a), HRNN achieves up to one order of magnitude lower query latency than the baselines. Fig. 5(b) further reveals the underlying reason: existing methods spend significantly more time verifying each candidate because they must compute the 𝑘NNradius online. These results demonstrate that online 𝑘NN-radius computation is a major bottleneck for existing R𝑘NN methods.

4

𝑚 =5

1

Θ =500

require exploring an extremely large neighborhood region. On GIST, certain queries need to scan more than 106 nearby neighbors before all R𝑘NN results can be identified. These observations indicate that relying solely on nearby neighbors is inefficient for R𝑘NN search.

Index Structure

We now present the key ideas for addressing the two limitations of existing R𝑘NN methods. Idea 1. To address Limitation 1, we revisit the relationship between 𝑘NN and R𝑘NN search. Existing methods often assume that nearby vectors tend to share common properties, and therefore treat the nearest neighbors of the query as candidates for R𝑘NN search. However, as shown in our analysis, nearby neighbors are often not true R𝑘NN results. Instead, we make a different assumption: a query’s R𝑘NN results can often be discovered through the R𝑘NN results of its nearby neighbors. This intuition is empirically validated in Fig. 6. This assumption follows from spatial proximity: as 𝑞 and its nearby neighbors lie close to each other, they are likely to fall within the 𝑘NN radius of the same point 𝑥. Thus, if 𝑥 is an R𝑘NN of 𝑞’s nearby neighbors, it is also likely to appear in the R𝑘NN sets of 𝑞. Based on this intuition, we first retrieve a set of nearby vectors as proxies. Rather than treating these proxies as R𝑘NN candidates, we leverage their reverse-neighbor lists, which provide their R𝑘NN results for arbitrary 𝑘, to generate candidates for the query. This

Definition 4.1 (HRNN Index). Given a dataset 𝐷 and a userdefined parameter K, the HRNN index is defined as I = (𝐺 HNSW, 𝐺 KNN, R), where: (1) 𝐺 HNSW is an HNSW graph constructed over 𝐷 (Definition 2.8); (2) 𝐺 KNN is a ranked KNN graph constructed over 𝐷 with parameter K (Definition 2.6); (3) R is the reverse-neighbor lists derived from 𝐺 KNN . For each vector 𝑜 ∈ 𝐷, its reverse-neighbor list R[𝑜] stores all pairs (𝑣, 𝑗) such that 𝑜 is the 𝑗-th nearest neighbor of 𝑣 in 𝐺 KNN (Definition 2.7). 6

Algorithm 3: Approximate R𝑘NN Search

(a)

(b)

Input: Index I = (𝐺 HNSW , 𝐺 KNN , R), query vector 𝑞, target parameter 𝑘, proxy size 𝑚, rank threshold Θ, HNSW search parameters 𝑒𝑝 and 𝑒 𝑓𝑠 Output: AR𝑘NN result set 𝑅 1 𝑅 ← ∅, 𝐶 ← ∅; 2 𝑁𝑚 (𝑞) ← Graph-Search(𝐺 HNSW , 𝑞, 𝑚, 𝑒𝑝, 𝑒 𝑓𝑠 ); 3 for 𝑏 ∈ 𝑁𝑚 (𝑞) do 4 for (𝑣, 𝑗 ) ∈ R(𝑏 ) in ascending order of 𝑗 do 5 if 𝑗 > Θ then break; 6 𝐶 ← 𝐶 ∪ {𝑣 };

(c)

Figure 7: An example of the HRNN index structure.

Example 4.2. Fig. 7 shows the components of HRNN. Fig. 7(a) shows the HNSW graph. Fig. 7(b) presents the ranked KNN graph, where each node 𝑜 maintains a list of K-nearest neighbors (K = 2), and each entry is denoted as (𝑣𝑖 , 𝛿 (𝑜, 𝑣𝑖 )). For instance, 𝑥 2 is the 1NN of 𝑥 3 with 𝛿 (𝑥 3, 𝑥 2 ) = 5. Fig. 7(c) shows the reverse-neighbor lists derived from 𝐺 KNN . For example, since 𝑥 3 is the 1NN of 𝑥 2 and the 2NN of 𝑥 1 , its reverse-neighbor list is R(𝑥 3 ) = {(𝑥 2, 1), (𝑥 1, 2)}, which records these reverse-neighbor relationships.

for 𝑜 ∈ 𝐶 do 𝑣𝑘 ← 𝐺 KNN [𝑜, 𝑘 ]; 9 𝑟ˆ𝑘 (𝑜 ) ← 𝛿 (𝑜, 𝑣𝑘 ); 10 if 𝛿 (𝑞, 𝑜 ) ≤ 𝑟ˆ𝑘 (𝑜 ) then 𝑅 ← 𝑅 ∪ {𝑜 }; 7

8

11

candidate set of query 𝑞 is defined as

Theorem 4.3. The HRNN index requires 𝑂 (|𝐷 | · 𝑀 · 𝐿 + |𝐷 | · K) space, where 𝐿 is the number of HNSW layers, 𝑀 is the maximum degree of the HNSW graph, and K is the number of ranked neighbors materialized per point.

𝐶𝑚,Θ (𝑞) =

⋃︂

{𝑣 | (𝑣, 𝑗) ∈ R[𝑏], 𝑗 ≤ Θ}.

(1)

𝑏 ∈𝑁𝑚 (𝑞)

A larger Θ increases candidate coverage and potentially improves recall, but incurs higher candidate-generation and verification costs. Note that K is the number of neighbors materialized in a ranked KNN graph, while Θ ≤ K is a query-time parameter controlling the number of entries scanned from each reverse-neighbor list.

Proof. The HRNN index consists of three components. First, the HNSW graph stores at most 𝑀 outgoing neighbors for each vector at each layer. Since there are at most |𝐷 | vectors and 𝐿 layers, the space required by the HNSW graph is bounded by 𝑂 (|𝐷 | · 𝑀 · 𝐿). Second, the ranked KNN graph stores K ranked neighbors for each vector, requiring 𝑂 (|𝐷 | · K) space. Third, the reverse-neighbor lists are obtained by transposing the ranked KNN graph. Each ranked neighbor entry generates exactly one reverse posting, yielding |𝐷 |·K reverse postings in total and therefore requiring 𝑂 (|𝐷 | · K) space. Summing the three components gives 𝑂 (|𝐷 | · 𝑀 · 𝐿 + 2|𝐷 | · K) = 𝑂 (|𝐷 | · 𝑀 · 𝐿 + |𝐷 | · K). □

4.2

return 𝑅;

Verification. After candidate generation, HRNN verifies whether each candidate 𝑜 ∈ 𝐶𝑚,Θ (𝑞) belongs to the final R𝑘NN result set of 𝑞. Existing methods typically compute the 𝑘NN-radius of each candidate online, which incurs substantial overhead. In contrast, HRNN leverages the pre-materialized ranked KNN graph 𝐺 KNN . Since the graph stores the top-K nearest neighbors of every vertex and K ≥ 𝑘, the 𝑘-th nearest neighbor of 𝑜 can be directly retrieved from 𝐺 KNN [𝑜]. Let 𝑣𝑘 denote this neighbor. The corresponding distance 𝑟ˆ𝑘 (𝑜) = 𝛿 (𝑜, 𝑣𝑘 ) serves as an estimate of the 𝑘NN-radius of 𝑜. Using this pre-materialized radius, a candidate 𝑜 is accepted if 𝛿 (𝑞, 𝑜) ≤ 𝑟ˆ𝑘 (𝑜). This verification process reduces candidate validation to a single distance comparison.

Query Processing

We now describe how to answer an approximate R𝑘NN query for a query vector 𝑞 using the proposed HRNN index I = (𝐺 HNSW, 𝐺 KNN, R). If the query vector 𝑞 were part of the indexed dataset 𝐷, its reverse-neighbor list R[𝑞] would directly reveal the points whose neighborhoods contain 𝑞. However, in practice, query vectors are typically not part of the indexed dataset. To address this issue, HRNN first retrieves a set of nearby points as proxies and uses their reverse-neighbor lists to approximate the unavailable reverse-neighborhood information of 𝑞.

Algorithm. Algorithm 3 presents the procedure for answering an approximate R𝑘NN query for a query vector 𝑞 using the hybrid index I = (𝐺 HNSW, 𝐺 KNN, R). The algorithm first performs an approximate 𝑚-nearest-neighbor search on 𝐺 HNSW to retrieve a set of proxy vertices 𝑁𝑚 (𝑞) that are close to 𝑞 (Line 2). The details of the graph search procedure are provided in Algorithm 2. For each proxy point 𝑏 ∈ 𝑁𝑚 (𝑞), the algorithm scans its reverse-neighbor list R(𝑏) in ascending rank order (Lines 3–4). Only vertices whose ranks do not exceed the threshold Θ are inserted into the candidate set 𝐶 (Lines 5–6). This proxy-guided reverse lookup generates candidate R𝑘NN results without expensive neighborhood expansion. The algorithm then verifies each candidate 𝑜 ∈ 𝐶 (Line 7). Specifically, it retrieves the 𝑘-th nearest neighbor 𝑣𝑘 of 𝑜 from 𝐺 KNN and obtains the corresponding estimated 𝑘NN-radius 𝑟ˆ𝑘 (𝑜) = 𝛿 (𝑜, 𝑣𝑘 ) (Lines 8–9). A candidate is accepted if 𝛿 (𝑞, 𝑜) ≤ 𝑟ˆ𝑘 (𝑜) (Line 10). All verified candidates are added to the result set 𝑅, which is returned as the final R𝑘NN result (Line 11).

Filter. Let 𝑁𝑚 (𝑞) = {𝑏 1, . . . , 𝑏𝑚 } denote the approximate 𝑚-nearest neighbors of 𝑞 returned by the HNSW graph. Rather than treating these points as R𝑘NN candidates, HRNN uses them to discover candidate points. To avoid scanning excessively large reverse-neighbor lists R[𝑏] of the proxy point 𝑏 ∈ 𝑁𝑚 (𝑞), we introduce a rank threshold Θ and only consider vectors whose ranks do not exceed Θ. This design is based on the intuition that if the rank of an object 𝑣 with respect to a proxy 𝑏 exceeds Θ, then 𝑏—and thus the query—is unlikely to be within the top-Θ nearest neighbors of 𝑣. Hence, 𝑣 can be safely pruned, as it is unlikely to be an RΘNN of 𝑞. Formally, the 7

Algorithm 4: HRNN Index Construction

(a)

(b)

❌

(c)

Input: Dataset 𝐷 ⊂ R𝑑 ; HNSW parameters 𝑀, 𝑒 𝑓𝑐 , and 𝑚𝐿 ; ranked KNN size K; NNDescent iterations 𝑇 Output: Index I = (𝐺 HNSW , 𝐺 KNN , R) // Phase 1: Build the HNSW graph 1 (𝐺 HNSW ,𝑊 ) ← Build-HNSW(𝐷, 𝑀, 𝑒 𝑓𝑐 , 𝑚 𝐿 ); // Phase 2: Construct the ranked KNN graph 2 Initialize 𝐺 KNN [𝑜 ] using 𝑊 [𝑜 ] for each 𝑜 ∈ 𝐷; 3 Execute Lines 2–11 of Algorithm 1 to build 𝐺 KNN ; // Phase 3: Construct reverse-neighbor lists 4 Initialize R(𝑜 ) ← ∅ for all 𝑜 ∈ 𝐷; 5 for each 𝑜 ∈ 𝐷 do 6 for 𝑗 ← 1 to K do 7 𝑣 ← 𝐺 KNN [𝑜, 𝑗 ]; 8 Append (𝑜, 𝑗 ) to R(𝑣);

✅

Figure 8: An example of the HRNN search process.

Example 4.4. Fig. 8 illustrates HRNN query processing for a query vector 𝑞, with 𝑚 = 2 and Θ = 1. The search first traverses 𝐺 HNSW and retrieves 𝑥 2 and 𝑥 3 as proxy vertices, as shown in Fig. 8(a). As illustrated in Fig. 8(b), HRNN then scans the reverseneighbor lists of the proxies in ascending rank order and inserts vertices whose rank does not exceed Θ into the candidate set 𝐶. In this example, 𝑥 1 , 𝑥 2 , 𝑥 3 , and 𝑥 6 are added to 𝐶. Finally, each candidate is verified by checking whether 𝑞 falls within its 𝑘NN-radius, which is obtained directly from 𝐺 KNN . Candidates satisfying this condition (e.g., 𝑥 3 ) are returned as R𝑘NN results.

for each 𝑜 ∈ 𝐷 do Sort R(𝑜 ) in ascending order of rank 𝑗;

11

return I = (𝐺 HNSW , 𝐺 KNN , R);

9

Theorem 4.5. Given a query vector 𝑞, Algorithm 3 answers the R𝑘NN query in expected time 𝑂 (log |𝐷 | + 𝑚 + 𝑠 (𝑞) + 𝑑 · 𝑢 (𝑞)), where 𝑚 is the proxy size, 𝑠 (𝑞) is the number of scanned reverseneighbor entries, and 𝑢 (𝑞) is the number of distinct candidates after deduplication (i.e., the size of 𝐶𝑚,Θ (𝑞) in Equation 1). Proof. Proxy retrieval over the HNSW graph requires 𝑂 (log |𝐷 | + 𝑚) expected time. Candidate generation scans 𝑠 (𝑞) reverse-neighbor entries and therefore takes 𝑂 (𝑠 (𝑞)) time. After deduplication, the algorithm verifies 𝑢 (𝑞) candidates. Each verification consists of one exact distance computation and one constanttime radius lookup, requiring 𝑂 (𝑑) time. Thus, verification costs 𝑂 (𝑑 · 𝑢 (𝑞)). Summing the three terms yields the stated bound. □

4.3

10

(a)

Before NNDescent

After NNDescent

(b)

(c)

(d)

Figure 9: An example of HRNN index construction.

𝑜, HNSW first performs graph search from the current entry point to retrieve a set of approximate nearest neighbors using Algorithm 2. These searched neighbors are then used to connect 𝑜 to existing vertices in different HNSW layers. Meanwhile, HRNN records the bottom-layer search results as 𝑊 [𝑜], which provides high-quality initial neighbor candidates for constructing the ranked KNN graph. Second, HRNN constructs the ranked KNN graph 𝐺 KNN (Lines 2–3). Instead of randomly initializing the neighbor list of each vertex, HRNN initializes 𝐺 KNN [𝑜] using 𝑊 [𝑜], i.e., the candidate neighbors obtained during HNSW construction. Then, Lines 2–11 of Algorithm 1 are executed to refine these initial lists via NNDescent to build a 𝐺 KNN . Third, HRNN builds the reverse-neighbor lists R from 𝐺 KNN (Lines 4). For each vertex 𝑜 and each rank position 𝑗 (Line 5–6), the algorithm obtains the 𝑗-th nearest neighbor 𝑣 = 𝐺 KNN [𝑜, 𝑗] (Line 7) and appends (𝑜, 𝑗) to R(𝑣) (Line 8). Finally, each reverse-neighbor list is sorted by rank 𝑗 (Line 9–10).

Index Construction

Constructing the HRNN index I = (𝐺 HNSW, 𝐺 KNN, R) is challenging because it consists of three coupled structures: the HNSW graph, the ranked KNN graph, and the reverse-neighbor lists. A straightforward approach is to construct them independently, but this would incur redundant neighborhood exploration and repeated nearestneighbor computations. To avoid this overhead, HRNN adopts a unified construction pipeline. It first builds the HNSW graph and records the neighbors discovered during the bottom-layer searches for each inserted vector. Since these neighbors already approximate the local neighborhood of the vector, they provide high-quality seeds for initializing its ranked KNN list. HRNN then applies NNDescent to refine these initial neighborhoods and construct a high-quality ranked KNN graph. Compared with random initialization, this strategy improves convergence and reduces construction cost. Finally, the reverseneighbor lists are derived by transposing the ranked KNN graph: if a vector 𝑢 is the 𝑗-th nearest neighbor of a vector 𝑣, the pair (𝑣, 𝑗) is inserted into the reverse-neighbor list of 𝑢. In this way, HRNN constructs all three index structures efficiently while maximizing the reuse of neighborhood information across different index views.

Example 4.6. Fig. 9 illustrates the construction process of the HRNN index. Fig. 9(a) shows the search performed when inserting a new point 𝑥 6 into 𝐺 HNSW , and 𝑥 6 is connected to 𝑥 2 after pruning the search results. Other points are inserted similarly. The search result [𝑥 2, 𝑥 3 ] is recorded and used to initialize the ranked KNN graph with K = 2, as shown in Fig. 9(b). Fig. 9(c) shows how NNDescent refines the ranked KNN graph. For example, in 𝑥 6 ’s neighbor list, the initial 2NN 𝑥 3 is replaced by the closer neighbor 𝑥 7 . Finally, Fig. 9(d) constructs the reverse-neighbor lists by scanning the refined ranked KNN graph. For instance, since 𝑥 2 appears as the 1NN of 𝑥 1 , 𝑥 3 , and 𝑥 6 , its reverse-neighbor list is R(𝑥 2 ) = [(𝑥 1, 1), (𝑥 3, 1), (𝑥 6, 1)].

Algorithm. Algorithm 4 constructs the HRNN index I = (𝐺 HNSW, 𝐺 KNN, R) in three phases. First, HRNN builds the HNSW graph 𝐺 HNSW over the dataset 𝐷 (Line 1). During HNSW construction, each point is inserted incrementally. For a newly inserted point 8

Theorem 4.7. Algorithm 4 constructs the HRNN index in expected (︁ )︁ time 𝑂 |𝐷 | · log |𝐷 | + 𝑇 · |𝐷 | · K2 · 𝑑 + |𝐷 | · K , where 𝑑 is the vector dimension, K is the ranked neighbor-list size, and 𝑇 is the number of NNDescent refinement iterations.

For every point 𝑥 ∈ 𝑆 ★ (𝑜 new ), inserting 𝑜 new modifies the ranked neighbor list of 𝑥, which subsequently triggers updates to reverseneighbor lists. However, computing 𝑆 ★ (𝑜 new ) exactly requires evaluating 𝛿 (𝑥, 𝑜 new ) for every point in the dataset, resulting in an 𝑂 (|𝐷 |) scan per insertion. Such a cost is impractical for large-scale vector collections.

Proof. Algorithm 4 consists of three phases. First, the algorithm builds the HNSW graph over 𝐷. HNSW inserts vectors incrementally. For each inserted vector, it performs graph search to locate candidate neighbors and then selects at most 𝑀 neighbors for graph construction. Following the standard logarithmic search behavior of HNSW, the expected cost of inserting one vector is 𝑂 (log |𝐷 |). Therefore, inserting all |𝐷 | vectors costs 𝑂 (|𝐷 | · log |𝐷 |). During this phase, HNSW also records the bottom-layer search results as initialization seeds for the ranked KNN graph. This recording is performed during HNSW construction and does not change the asymptotic cost. Second, HRNN constructs the ranked KNN graph. Each vector maintains a ranked list of K neighbors. The initial lists are obtained from the HNSW search results and are refined using NNDescent. In each refinement iteration, for each vector, NNDescent compares candidate pairs generated from its forward and reverse neighbor lists. Since each list has size at most K, the number of candidate comparisons per vector is 𝑂 (K2 ). Each comparison requires computing the distance between two 𝑑-dimensional vectors, which costs 𝑂 (𝑑). Hence, one NNDescent iteration costs 𝑂 (|𝐷 | · K2 · 𝑑). After 𝑇 iterations, the total refinement cost is 𝑂 (𝑇 · |𝐷 | · K2 · 𝑑). Third, HRNN constructs the reverse-neighbor lists by transposing the ranked KNN graph. Since each of the |𝐷 | vectors stores K ranked neighbors, the ranked KNN graph contains exactly |𝐷 | · K directed neighbor entries. For each entry, HRNN inserts one corresponding reverse posting. Thus, materializing the reverse-neighbor lists costs 𝑂 (|𝐷 | · K). Summing the costs of the three phases gives the result. □

4.4

Approximate Affected Area. To avoid exhaustive scans, HRNN adopts the same proxy principle used during query processing. Intuitively, points close to 𝑜 new tend to share similar reverse-neighbor relationships and therefore provide effective hints about the affected region. During HNSW insertion, HRNN obtains a set of nearby proxy points 𝑁𝑚𝑢 (𝑜 new ) and records the search result 𝑊 (𝑜 new ) used to initialize the ranked neighbor list of 𝑜 new . Given an updatetime rank threshold Θ𝑢 ≤ K, HRNN constructs an approximate affected set by scanning the reverse-neighbor lists of these proxies: ⋃︂ 𝑆ˆ𝑢 (𝑜 new ) = {𝑥 | (𝑥, 𝑗) ∈ R(𝑏), 𝑗 ≤ Θ𝑢 }. (3) 𝑏 ∈𝑁𝑚𝑢 (𝑜 new )

The parameter Θ𝑢 controls the trade-off between maintenance cost and update quality. Larger values increase the coverage of the affected region but require scanning more reverse-neighbor entries. Maintenance Procedure. After identifying the approximate affected set, HRNN incrementally updates all index components. Specifically, 𝑜 new is first inserted into the HNSW graph, and the collected search result 𝑊 (𝑜 new ) is used to initialize its ranked neighbor list in 𝐺 KNN . Next, HRNN examines each point 𝑥 ∈ 𝑆ˆ𝑢 (𝑜 new ). If 𝛿 (𝑥, 𝑜 new ) is smaller than the distance to the current K-th neighbor of 𝑥, the new vector is inserted into 𝐺 KNN [𝑥]. If the list already contains K entries, the current farthest neighbor is evicted. Whenever a neighbor list changes, the corresponding reverse-neighbor lists are updated by removing obsolete entries, inserting new entries, and adjusting the ranks of shifted neighbors. Since the affected area is identified approximately rather than exactly, the maintained index may differ slightly from one obtained through full batch reconstruction. However, as demonstrated in Section 5, this discrepancy is negligible in practice. Periodic reconstruction can be performed when necessary to restore the index to its batch-built state.

Index Maintenance

Real-world vector datasets are rarely static. New vectors are continuously generated in applications such as retrieval-augmented generation and recommendation systems. Rebuilding the entire HRNN index after each insertion is prohibitively expensive. Given a newly inserted point 𝑜 new , maintenance must synchronize three coupled structures. First, 𝑜 new must be incorporated into the HNSW graph to support future proxy retrieval. Second, if 𝑜 new becomes one of the top-K nearest neighbors of existing vectors, the corresponding ranked neighbor lists in 𝐺 KNN must be updated. Third, all affected reverse-neighbor lists must be refreshed to remain consistent with the updated ranked KNN graph. Thus, we first insert 𝑜 new into 𝐺 HNSW and then describe how to minimize the maintenance cost of updating 𝐺 KNN and R.

Algorithm. Algorithm 5 incrementally maintains the HRNN index after the arrival of a new vector 𝑜 new . The procedure updates the three coupled structures of HRNN: the HNSW graph 𝐺 HNSW , the ranked KNN graph 𝐺 KNN , and the reverse-neighbor lists R. In Phase 1, the algorithm inserts 𝑜 new into 𝐺 HNSW and reuses the search result 𝑊 (𝑜 new ) produced during HNSW insertion (Lines 1– 2). The top-𝑚𝑢 closest vectors in this set are selected as proxy vectors 𝑁𝑚𝑢 (𝑜 new ), which serve as proxies for identifying the affected region. In Phase 2, the algorithm constructs the approximate affected area 𝑆ˆ𝑢 (𝑜 new ) (Lines 3–8). For each proxy vector 𝑏, it scans the reverse-neighbor list R(𝑏) in ascending rank order and collects the owner vectors whose ranks do not exceed the threshold Θ𝑢 . This step follows the same proxy principle used during query processing and avoids the expensive computation of the exact affected area. In Phase 3, the algorithm initializes the ranked neighbor list of 𝑜 new using the top-K vectors from 𝑊 (𝑜 new ) (Lines 9–14). The resulting neighborhood is inserted into 𝐺 KNN , and the corresponding reverse-neighbor entries are added to R. Finally, in Phase 4, the algorithm refreshes the neighborhoods of all vectors in 𝑆ˆ𝑢 (𝑜 new )

Exact Affected Area. The key challenge is identifying the existing points in dataset 𝐷 affected by the insertion of 𝑜 new . Let 𝑟 K (𝑜) denote the distance from 𝑜 to its current K-th nearest neighbor in 𝐺 KNN . A vector 𝑥 is affected if 𝑜 new should appear in its top-K neighbor list after insertion. Formally, the exact affected set is 𝑆 ★ (𝑜 new ) = {𝑥 ∈ 𝐷 | 𝛿 (𝑥, 𝑜 new ) < 𝑟 K (𝑥)}.

(2) 9

Table 3: Dataset statistics.

Algorithm 5: HRNN Index Insertion Maintenance Input: Index I = (𝐺 HNSW , 𝐺 KNN , R), new vector 𝑜 new , update parameters 𝑚𝑢 , Θ𝑢 Output: Updated index I // Phase 1: Insert into HNSW and collect proxy vectors 1 (𝐺 HNSW ,𝑊 (𝑜 new ) ) ← HNSW-Insert(𝐺 HNSW , 𝑜 new ); 2 𝐵𝑚𝑢 (𝑜 new ) ← top-𝑚𝑢 closest vectors in 𝑊 (𝑜 new ) to 𝑜 new ; // Phase 2: Construct the approximate affected area 3 𝑆ˆ𝑢 (𝑜 new ) ← ∅; 4 for each 𝑏 ∈ 𝐵𝑚𝑢 (𝑜 new ) do 5 for each (𝑥, 𝑗 ) ∈ R(𝑏 ) in ascending order of 𝑗 do 6 if 𝑗 > Θ𝑢 then break; 7 𝑆ˆ𝑢 (𝑜 new ) ← 𝑆ˆ𝑢 (𝑜 new ) ∪ {𝑥 };

Dataset SIFT Msong GIST MSMARCO

// Phase 3: Initialize the new vector 𝐿new ← top-K vectors in 𝑊 (𝑜 new ) ranked by 𝛿 (𝑜 new , ·); 9 𝐺 KNN [𝑜 new ] ← 𝐿new ; 10 for each 𝑣 ∈ 𝐿new do 11 𝑗 ← rank of 𝑣 in 𝐿new ; 12 Insert (𝑜 new , 𝑗 ) into R(𝑣), keeping R(𝑣) sorted by rank;

23

24

# Query

Domain

128 420 960 1024

1.0M 1.0M 1.0M 1.0M

10,000 1,000 1,000 1,000

Images Audio Images Text Embeddings

Remark. Building an HRNN index solely through incremental insertions is feasible, but incurs the cumulative cost of maintaining the index after each update. Unlike batch construction in Algorithm 4, which amortizes neighbor refinement through a onetime NNDescent procedure, insertion-based construction performs affected-area discovery and reverse-neighbor-list synchronization for each arriving point. Consequently, its total cost depends on the distribution of update proxies, the sizes of the affected areas, and the number of modified reverse-neighbor lists. As shown in our experiments, insertion-only construction is slower than batch construction on static datasets. However, it avoids expensive index rebuilding and supports continuous updates while preserving the same index structure and query processing algorithm.

// Phase 4: Refresh affected neighborhoods 13 for each 𝑥 ∈ 𝑆ˆ𝑢 (𝑜 new ) do 14 𝐿old ← 𝐺 KNN [𝑥 ]; 15 𝑟 K (𝑥 ) ← 𝛿 (𝑥, 𝐺 KNN [𝑥, K] ); 16 if 𝛿 (𝑥, 𝑜 new ) < 𝑟 K (𝑥 ) then 17 𝐿upd ← TopK(𝐿old ∪ {𝑜 new } ) ranked by 𝛿 (𝑥, ·); 18 𝐺 KNN [𝑥 ] ← 𝐿upd ; 19 for each 𝑣 ∈ 𝐿old \ 𝐿upd do 20 Remove (𝑥, ·) from R(𝑣); 22

# Base

entries. This step costs 𝑂 (𝑠𝑢 ). Third, for each vector 𝑥 ∈ 𝑆ˆ𝑢 (𝑜 new ), HRNN checks whether 𝑜 new enters the top-K neighbor list of 𝑥. Each check requires one exact distance computation 𝛿 (𝑥, 𝑜 new ) over 𝑑 dimensions and one comparison with the current K-th neighbor distance. Thus, this step costs 𝑂 (𝑑 · |𝑆ˆ𝑢 (𝑜 new )|). Finally, suppose 𝑎𝑢 existing ranked neighbor lists are updated. Refreshing one changed list may shift at most K ranked positions and therefore touches 𝑂 (K) reverse-neighbor entries. In addition, the ranked neighbor list of 𝑜 new is initialized and materialized, which costs 𝑂 (K). Hence, the synchronization cost is 𝑂 ((𝑎𝑢 + 1) · K). Summing the four terms gives the total cost. □

8

21

Dimension

for each 𝑣 ∈ 𝐿upd do 𝑗 ← rank of 𝑣 in 𝐿upd ; Insert or update (𝑥, 𝑗 ) in R(𝑣), keeping R(𝑣) sorted by rank;

5 EXPERIMENT 5.1 Experimental Setup

return I;

(Lines 15–30). For each vector 𝑥, it first retrieves the current KNNradius 𝑟 K (𝑥). If 𝛿 (𝑥, 𝑜 new ) < 𝑟 K (𝑥), the new vector belongs to the top-K neighborhood of 𝑥. The algorithm therefore inserts 𝑜 new into 𝐺 KNN [𝑥], removes the farthest neighbor if necessary, and constructs the updated ranked neighbor list. It then synchronizes the reverse-neighbor lists by removing obsolete postings and inserting or updating the postings associated with the modified neighborhood. Consequently, the ranked KNN graph and reverse-neighbor lists remain consistent after each insertion.

Datasets. We evaluate on four real-world vector datasets: SIFT [26], Msong [34], GIST [24], and MSMARCO [35]. SIFT, Msong, and GIST are standard benchmarks widely used in prior approximate R𝑘NN studies [41], while MSMARCO represents modern text-embedding retrieval workloads. Table 3 summarizes the dataset statistics. Due to the 𝑂 (|𝐷 | 2 ) cost of generating exact R𝑘NN ground truth, following prior work [41], our main experiments use datasets with 1 million vectors. To evaluate scalability, we further evaluate HRNN on datasets containing up to 10 million vectors in Exp-8.

Theorem(︂ 4.8. For an insertion of 𝑜 new , the maintenance cost of )︂ HRNN is 𝑂 log |𝐷 | + 𝑠𝑢 + 𝑑 · |𝑆ˆ𝑢 (𝑜 new )| + (𝑎𝑢 + 1) · K , where 𝑠𝑢 is the number of scanned reverse-neighbor entries, 𝑆ˆ𝑢 (𝑜 new ) is the approximate affected set, and 𝑎𝑢 is the number of existing ranked neighbor lists updated.

Compared Methods. We compare HRNN against representative graph-based approximate R𝑘NN methods, including SFT, RDT, and the state-of-the-art HAMG [41]. Following HAMG, we implement SFT and RDT on top of HNSW to provide strong high-dimensional baselines. We do not compare against spatial-partitioning methods [42, 43, 51] or tree-based R𝑘NN methods [1, 52], as prior studies have shown them to be prohibitively expensive on million-scale high-dimensional datasets.

Proof. The maintenance procedure has four parts. First, HRNN inserts 𝑜 new into the HNSW graph, and one insertion costs 𝑂 (log |𝐷 |). Second, HRNN discovers the approximate affected set by scanning the rank-truncated reverse-neighbor lists of the update proxies. Let 𝑠𝑢 denote the number of scanned reverse-neighbor

• HAMG. The state-of-the-art AR𝑘NN method [41]. Since the original Java implementation is not publicly available and the paper does not fully specify all dataset-specific parameter settings, we 10

re-implement HAMG in C++ based on the published algorithm description. We tune both construction and query parameters over the ranges reported in [41], as well as larger budgets, and report the best recall–latency trade-off achieved on our platform. • HNSW-SFT. The SFT-style baseline used in HAMG [39, 41]. It first retrieves an expanded set of 𝑘 ′ nearest neighbors of the query using HNSW and then verifies each candidate for R𝑘NN membership. • HNSW-RDT. The RDT baseline [6, 41] implemented on top of HNSW, following the design adopted in HAMG. It incrementally explores unchecked nearest neighbors around the query and applies the pruning and termination rules of RDT.

These results expose the limitations of existing methods for highdimensional R𝑘NN search, especially on datasets with a pronounced mismatch between nearby neighbors and true R𝑘NN results. By using nearby neighbors as proxies instead of direct candidates and verifying only reverse-lookup candidates with pre-materialized 𝑘NNradius information, HRNN substantially reduces both candidategeneration and verification overhead, yielding consistently better recall–throughput trade-offs. Exp-2: Query Time Breakdown. We analyze how query time is distributed across different stages of HRNN. We decompose each query into three phases: (1) proxy retrieval using the navigation graph 𝐺 HNSW , (2) reverse-neighbor list scanning for candidate generation, and (3) candidate verification using pre-materialized 𝑘NNradius retrieved from the ranked 𝑘NN graph 𝐺 KNN . For each dataset, we select the lowest-latency configuration from the same (𝑚, Θ) grid used in Exp-1 under Recall@10 thresholds of 0.95 and 0.99. Fig. 11 shows that proxy retrieval incurs a small and nearly constant cost across datasets and recall targets, ranging from 0.43ms to 1.7ms. Reverse-neighbor list scanning also remains lightweight because HRNN accesses only rank-truncated posting entries. In contrast, candidate verification becomes the dominant cost at high recall levels, as more candidates must be validated. For example, verification accounts for 78.5%–86.3% of the total query time on GIST and increases from 35.7% to 74.3% on MSMARCO as the target recall rises from 0.95 to 0.99. Nevertheless, compared with existing methods (see also Fig. 5), HRNN reduces verification overhead by replacing expensive online 𝑘NN-radius computation with direct lookups from the materialized ranked 𝑘NN graph, thereby mitigating one of the major bottlenecks of prior R𝑘NN approaches.

Metrics. We evaluate both efficiency and accuracy. Query performance is measured by average queries per second (QPS) over all queries, while accuracy is measured by Recall@𝑘. For index construction, we report construction time and index size. A construction process is terminated if its runtime exceeds 104 seconds. Implementation. We implement all methods in C++ and compile them using GCC 13.1.0. Experiments are conducted on a server equipped with an Intel Xeon Platinum 8352V CPU @ 2.10GHz and 512 GB RAM running Ubuntu 20.04 LTS. Following common practice in vector search studies [14, 23, 33, 41, 49], all query experiments are executed using a single thread, while index construction uses 64 threads. For HRNN, the HNSW graph is constructed with 𝑀 = 16 and 𝑒 𝑓𝑐 = 400. For the baselines, we tune parameters according to the ranges reported in their original papers and use 𝐶 = 8000 and 𝑑𝑚 = 80 for HAMG, and 𝑒 𝑓𝑐 = 400 for HNSW-RDT and HNSW-SFT.

Exp-3: Index Construction Time and Space Consumption. We next compare the index construction time and index size of different methods. The results are reported in Table 4 and Table 5, respectively. Table 4 compares the construction cost of graph HNSW, index HRNN, and index HAMG. Compared with the graph HNSW, HRNN incurs additional offline overhead to construct the ranked KNN graph and materialize the reverse-neighbor lists. Nevertheless, it remains substantially cheaper to build than HAMG. Across the four datasets, HAMG requires 5.2–14.4× longer construction time than HRNN, with the largest gap observed on MSMARCO. Table 5 reports the index size of different methods. The Base column shows the raw vector storage size as a reference, while the method columns report index overhead only and exclude the raw vectors. HRNN stores both the navigation graph and the reverseneighbor lists derived from the ranked KNN graph. As a result, it requires more memory than HNSW. This overhead is most pronounced on low-dimensional datasets such as SIFT, where the raw vector storage is relatively small. On higher-dimensional datasets, the overhead becomes more moderate. For example, the total space consumption of HRNN is only 1.54× and 1.52× the raw vector size on GIST and MSMARCO, respectively.

Parameter Settings. Unless otherwise specified, all experiments evaluate AR𝑘NN search with 𝑘 = 10. For HRNN, we construct a single index per dataset with K = 500. HRNN has two query-time parameters: the number of proxies 𝑚 and the reverse-neighbor threshold Θ. To generate the recall–throughput trade-off curves in Exp-1, we evaluate 𝑚 ∈ {1, 3, 5, 10, 20, 30, 50, 100, 150, 200} and Θ ∈ {10, 20, 30, 50, 100, 200, 300, 500}. Each reported HRNN point corresponds to a specific (𝑚, Θ) configuration. For experiments requiring a single configuration at a target recall threshold 𝜏, we select the configuration that achieves the highest throughput among all evaluated settings satisfying Recall@𝑘 ≥ 𝜏.

5.2

Experimental Results

Exp-1: Query Performance Comparison. We first compare the end-to-end recall–throughput trade-off of all methods. Fig. 10 reports the results of HRNN, HAMG, HNSW-SFT, and HNSWRDT on the four datasets. On MSMARCO, at Recall@10 above 0.99, HRNN achieves 185 QPS, outperforming HAMG, HNSWSFT, and HNSW-RDT by 83.1×, 10.3×, and 23.3×, respectively. On GIST, HAMG achieves only 0.714 recall. Although HNSW-SFT and HNSW-RDT can further improve recall by expanding the querycentered search region, their throughput drops to roughly 1 QPS or below. Specifically, HNSW-SFT reaches 0.958 recall at only 0.372 QPS, while HNSW-RDT reaches 0.880 recall at 1.076 QPS. We therefore terminate further expansion once the throughput becomes prohibitively low. In contrast, HRNN achieves 0.999 recall at 39.3 QPS.

Exp-4: Parameter Sensitivity. We study the impact of HRNN’s two query-time parameters: the number of proxies 𝑚 and the reverse-neighbor threshold Θ. Both parameters increase candidate coverage but affect different stages of the search process. Specifically, a larger 𝑚 expands the set of query-side proxies, while a larger 11

HAMG

HRNN

101 0.4

0.6

0.8

102 101 100 0.4

1

Recall@10

HNSW-RDT

103

(a) SIFT

0.6

0.8

Recall@10

QPS (1/s)

102

HNSW-SFT

103 QPS (1/s)

103

QPS (1/s)

QPS (1/s)

103

102 101 100

1

0.4

(b) GIST

0.6

0.8

Recall@10

1

102 101 0.4

(c) MSONG

0.6

0.8

Recall@10

1

(d) MSMARCO (1M)

Figure 10: Query performance comparison: Recall@10 vs. QPS.

1 0.5 0

1.5

1 0.5 0

0.95 0.99 Target Recall@10

0.99 Target Recall@10

(b) Msong Latency (ms)

Latency (ms)

(a) SIFT 20 15 10 5 0

Table 6: Best HRNN parameter configurations for target recall@10.

Phase 3 Verify

Phase 2 R List Scan Latency (ms)

Latency (ms)

Phase 1 Proxy Retrieval

0.95 0.99 Target Recall@10

6 2

(c) GIST

(d) MSMARCO-1M

Table 4: Index construction time (seconds). HNSW

HRNN

HAMG

49 91 229 199

185 280 452 553

954 1537 4286 7947

SIFT Msong GIST MSMARCO

Recall@10 ≥ 0.99 (𝑚, Θ) Recall / QPS

GIST SIFT MSMARCO Msong

(10, 500) (20, 100) (30, 100) (3, 10)

(50, 300) (50, 100) (50, 500) (3, 10)

0.9622 / 105.1 0.9646 / 1561.8 0.9599 / 607.5 0.9990 / 1253.1

0.9935 / 53.4 0.9916 / 1015.5 0.9919 / 184.5 0.9990 / 1253.1

Exp-5: Ablation Study. We conduct ablation studies to evaluate the impact of the key components of HRNN. Specifically, we examine three variants: (1) replacing 𝐺 HNSW for proxy retrieval, (2) constructing the ranked 𝐺 KNN without using the neighbor seeds collected from 𝐺 HNSW , and (3) performing candidate verification without pre-materialized 𝑘NN-radius information. Navigation graph replacement. We first replace the HNSW graph used for proxy retrieval while keeping all other components unchanged. Fig. 13 compares HNSW and NSG. On GIST, the two graphs achieve similar performance in the high-recall region. At Recall@10 around 0.99, HNSW achieves 0.9906 recall at 63.9 QPS, while NSG achieves 0.9907 recall at 67.9 QPS. On SIFT, both graphs reach comparable recall, but HNSW delivers higher throughput. At Recall@10 around 0.99, HNSW achieves 0.9910 recall at 1441.8 QPS, compared with 0.9917 recall at 1082.5 QPS for NSG. These results indicate that HRNN is not tied to a specific navigation graph, although the choice of graph affects query latency. KNN graph construction with HNSW-Seeding. We next evaluate how the ranked KNN graph is initialized prior to NNDescent refinement. Fig. 14 compares standard NNDescent with random initialization against HRNN’s HNSW-seeded construction. On GIST, random initialization reaches only 0.9066 KNNG recall after 435 s of refinement. In contrast, reusing HNSW insertion candidates as seeds yields an initial recall of 0.4880 and converges to perfect recall after 310.85 s. A similar trend is observed on SIFT, where the final recall/construction time improves from 0.9874/387.47 s to 1.0/272.51 s. These results demonstrate that the HNSW insertion process provides high-quality initialization for NNDescent, reducing refinement cost while improving the quality of the resulting ranked KNN graph. 𝑘NN-radius materialization. Finally, we evaluate whether HRNN can remove or approximate its materialized radius information. Table 7 reports results on GIST with 𝑚 = 20, Θ = 500, and 𝑘 = 10. The Gold Radius variant replaces HRNN’s 𝐺 KNN -derived radius estimates 𝑟ˆ𝑘 (𝑥) with exact radius 𝑟𝑘 (𝑥) computed by brute force. Recall changes only marginally, from 0.9879 to 0.9880, indicating that the ranked KNN graph provides sufficiently accurate radius

0.95 0.99 Target Recall@10

Figure 11: Query time breakdown at recall@10 targets (0.95 and 0.99).

Dataset

Recall@10 ≥ 0.95 (𝑚, Θ) Recall / QPS

all datasets, reflecting the trade-off between candidate coverage and query efficiency.

4 0

Dataset

Table 5: Index space consumption (MB). Dataset

Base

HNSW

HAMG

HRNN

HRNN Total/Base

SIFT Msong GIST MSMARCO

512.0 1670.2 3840.0 4096.0

100.7 83.3 71.8 103.4

206.6 165.2 199.9 275.3

2112.6 2083.4 2083.8 2114.9

5.13× 2.25× 1.54× 1.52×

Θ relaxes the rank constraint when scanning reverse-neighbor lists. Since the ranked KNN graph is constructed offline with a fixed size of K = 500, all settings satisfying Θ ≤ K are supported by the same index. Table 6 reports the highest-throughput configurations that satisfy Recall@10 thresholds of 0.95 and 0.99. The optimal parameter settings vary across datasets. For example, Msong saturates with (𝑚, Θ) = (3, 10), whereas GIST requires larger candidate coverage, reaching Recall@10 ≥ 0.99 only with configurations such as (300, 50). SIFT and MSMARCO exhibit intermediate behavior. These results reflect the degree of mismatch between nearby neighbors and R𝑘NN results, with larger mismatches requiring larger values of (𝑚, Θ). Importantly, HRNN can adapt to such variations by adjusting (𝑚, Θ) at query time, without rebuilding the index. Fig. 12 reports the complete (𝑚, Θ) parameter grid evaluated in our experiments. Increasing either 𝑚 or Θ generally improves Recall@10, but reduces throughput. This trend is consistent across 12

GIST

SIFT

MSMARCO

Msong

500

1.0 0.8

200 100

0.6

Recall@10

Recall@10

300

50 30

0.4

20

0.2

10

0.0 500

103

300

QPS (log scale)

QPS

200 100 50

102

30 20

30

20

5 10

3

1

m

50 10 0 15 0 20 0

m

50 10 0 15 0 20 0

30

20

5 10

3

1

30

20

5 10

3

1

m

50 10 0 15 0 20 0

m

50 10 0 15 0 20 0

30

20

5 10

3

1

10

Figure 12: Recall@10 (top) and QPS (bottom, log scale) over the evaluated (𝑚, Θ) parameter grid.

0.95 0.96 0.97 0.98 0.99

103 0.96

1

Recall@10

(a) GIST (𝑑 =960)

0.97

0.98

Recall@10

0.99

1

0

0

200

NNDescent time (s)

400

(a) GIST (𝑑 =960)

100

200

300

NNDescent time (s)

400

(b) SIFT (𝑑 =128)

Figure 14: Effect of HNSW-seeding on KNN graph construction.

HRNN Gold Radius No reverse-neighbor Lists

Recall@10

Latency (ms)

Avg. Results

0.9879 0.9880 0.9998

14.74 14.39 372.04

9.89 9.84 9.96

1,000 100 1

10

30 50 90

𝑘

(b) Target Recall@𝑘 : 0.99

Exp-7: Insertion-Based Maintenance. We evaluate insertionbased maintenance by varying the initial batch fraction 𝑠: the first 𝑠 · 𝑛 points are batch-built and the remaining points are inserted. Thus 𝑠 = 1 is pure batch construction and 𝑠 = 0 is pure insertion construction. For each 𝑠, we report the highest-QPS operating point reaching each target Recall@10. Fig. 16 shows that insertion-based maintenance largely preserves the recall-QPS trade-off. On SIFT, pure insertion reaches 1429, 1266, and 775 QPS at Recall@10 targets 0.90, 0.95, and 0.99, respectively, compared with 1786, 1370, and 813 QPS for pure batch construction (that is, the index is constructed once over the entire dataset). On GIST, pure insertion is comparable to pure batch at the 0.90 and 0.95 targets, reaching 140/89 QPS versus 133/86 QPS. The maintained index thus does not collapse as the insertion fraction grows. The main overhead is construction time, and this overhead is expected because insertion-based construction synchronizes multiple materialized views after each arriving point. Building entirely through insertions costs 155s versus 86s on SIFT and 760s versus

Table 7: 𝑘NN-radius materialization ablation on GIST-1M. Variant

30 50 90

MSMARCO

Figure 15: Performance of HRNN across different 𝑘 values.

0.5 0

Msong

on SIFT, from 61 to 36 QPS on GIST, and from 279 to 105 QPS on MSMARCO. On Msong, the Recall@𝑘 ≥ 0.95 and Recall@𝑘 ≥ 0.99 curves coincide because the lowest-latency configuration already achieves Recall@𝑘 ≈ 0.999 for all evaluated values of 𝑘, while maintaining a throughput of approximately 800–930 QPS. These results demonstrate that HRNN remains robust across a wide range of target 𝑘 values. Cross-method comparisons are reported separately in Exp-1 under the common setting of 𝑘 = 10.

1

0

10

𝑘

HNSW seed + NNDescent KNNG recall@10

KNNG recall@10

0.5

100

(a) Target Recall@𝑘 : 0.95

Figure 13: Effect of navigation graph choice (HNSW vs. NSG).

1

1,000

1

(b) SIFT (𝑑 =128)

Random init + NNDescent

GIST QPS (1/s)

101.6

QPS (1/s)

QPS (1/s)

QPS (1/s)

101.8

SIFT

NSG

HNSW (default)

102

estimates for verification. Removing the reverse-neighbor lists (i.e., the variant No Reverse-neighbor Lists) forces HRNN to verify all 1M data points, increasing latency from 14.74 ms to 372.04 ms. This confirms that reverse-neighbor lists are essential for selective candidate generation and efficient verification. Exp-6: Varying 𝑘. We evaluate HRNN under standard R𝑘NN settings with varying values of 𝑘 ∈ 1, 10, 30, 50, 90. For each dataset and each value of 𝑘, we evaluate the same (𝑚, Θ) parameter grid used in Exp-1 and report the highest-throughput configuration satisfying target Recall@𝑘 thresholds of 0.95 and 0.99. Fig. 15 shows that HRNN maintains stable recall–throughput trade-offs across the entire range of 𝑘. At the 0.99 recall target, increasing 𝑘 from 1 to 90 reduces throughput from 1245 to 400 QPS 13

𝑟 ≥ 0.90

𝑟 ≥ 0.95

SIFT

2M

GIST

6M

1

0

(a) SIFT

0.5 𝑠

1

(b) GIST

0

0

0.5 𝑠

1

0.85

HNSW-SFT

103

QPS (1/s)

QPS (1/s)

102 101 2M 4M 6M 8M 10M |𝐷 | (M)

(a) SIFT (d=128)

102 0.95

Recall@10

1

(a) SIFT (d=128)

HNSW-RDT

0.85

0.9

0.95

Recall@10

1

(b) MSMARCO (d=1024)

HRNN

HAMG

HNSW

104

102 101 100

0.9

Figure 18: Scalability of HRNN across dataset sizes.

Build time (s)

HAMG

103

102.5

(c) Build time

Figure 16: Impact of maintenance on query throughput and construction time. Panels (a)–(b) show throughput at Recall@10 targets of 0.90, 0.95, and 0.99; panel (c) shows total construction time.

HRNN

103

2M 4M 6M 8M 10M |𝐷 | (M)

Build time (s)

0.5 𝑠

10M

QPS (1/s)

40 0

QPS (1/s)

400

80

8M

103

Build time (s)

QPS (1/s)

120

1,200

103 102

104 103

(b) MSMARCO (d=1024) 2M 4M 6M 8M 10M |𝐷 | (M)

Figure 17: Cross-method scalability at recall@10 ≥ 0.95.

170s on GIST, i.e., 1.80× and 4.47× more than pure batch construction. This cost comes from maintaining the HNSW graph, ranked KNN graph, materialized radius estimates, and reverse-neighbor lists during insertion. Overall, HRNN supports continuous arrivals by paying additional write-side maintenance cost while keeping search efficiency stable.

(a) SIFT (d=128)

2M 4M 6M 8M 10M |𝐷 | (M)

(b) MSMARCO (d=1024)

Figure 19: Index construction scalability across dataset sizes.

For most existing methods, the verification stage is similar: they issue a standard 𝑘NN search for each candidate to determine whether the candidate belongs to the R𝑘NN result set of the query vector. Therefore, existing methods mainly differ in how they generate the candidate set. Based on this distinction, we categorize existing methods into three groups below.

Exp-8: Scalability to 10M Vectors. We evaluate scalability on the SIFT and MSMARCO datasets with sizes |𝐷 | ∈ {2, 4, 6, 8, 10}M. We compare HRNN, HNSW-SFT, and HNSW-RDT across all dataset sizes. For HAMG, we report only completed runs; larger instances are omitted when construction time exceeds 104 seconds and query throughput remains below 10 QPS. Fig.17 compares query throughput at a common target of Recall@10 ≥ 0.95. On SIFT, HRNN is 1.59– 3.74× faster than HNSW-SFT and 8.4–11.9× faster than HNSWRDT across all dataset sizes. The advantage over HAMG is even more pronounced. For example, on SIFT-6M, HRNN achieves 834.3 QPS, whereas HAMG achieves only 1.96 QPS. These results demonstrate the superior scalability of HRNN on large-scale datasets. Fig. 18 shows that HRNN maintains a stable recall–throughput trade-off up to 10M vectors. At Recall@10 ≥ 0.95, HRNN achieves 842 QPS on SIFT-10M and 360.2 QPS on MSMARCO-10M. It further reaches Recall@10 = 0.9975 on SIFT-10M while sustaining 211.7 QPS. Fig. 19 reports index construction time as the dataset size increases. On SIFT-10M, HRNN builds the index in 2335 s, compared with 559 s for HNSW. On MSMARCO-10M, HRNN requires 5006 s, compared with 2433 s for HNSW. This additional offline cost stems from constructing the ranked KNN graph and materializing the reverse-neighbor lists. Nevertheless, it remains substantially lower than that of HAMG, which already requires 11405 s on SIFT-6M and 37837 s on MSMARCO-4M.

6

4M

800

1,700

700

𝑟 ≥ 0.99

Classical Methods. Early studies mainly focused on exact R𝑘NN search in low-dimensional vector spaces. One category is partitionbased methods [42, 43, 51, 57], which divide the data space into geometric regions such as half-spaces or influence zones. These methods prune impossible candidates based on the spatial partition and the relative position between the query vector and the partitioned regions. Another category is precomputation-based methods [1, 52]. These methods typically use tree-based spatial indexes (e.g., M-trees) and derive conservative distance bounds for subtrees to prune unpromising points during query processing. However, these classical methods suffer severely from the curse of dimensionality. In high-dimensional spaces, partition-based methods lose their discriminative power and often degenerate into scanning large portions of the dataset. Precomputation-based methods also incur high index construction and maintenance costs due to expensive distance-bound computation. Expansion-Based Methods. To scale R𝑘NN queries to highdimensional vectors, expansion-based methods such as SFT [39] and RDT [6] were proposed. These methods aim to find approximate R𝑘NN results by progressively exploring nearby neighbors around the query vector 𝑞 until a stopping condition is satisfied. As analyzed in Section 3, these methods become inefficient when nearby neighbors do not align well with the true R𝑘NN results, since they must explore a large neighborhood region to maintain high search accuracy.

RELATED WORK

As introduced in Section 3, existing methods for (approximate) R𝑘NN search generally follow a filter-and-verification framework.

The State-of-the-Art and Beyond. The state-of-the-art method HAMG [41] adapts proximity graphs for R𝑘NN search. HAMG 14

leverages the key property of the MRN graph that guarantees true R𝑘NN results lie within the 𝑘-hop neighborhood of the query vector on the graph. Based on this property, HAMG retrieves nearby graph neighbors as candidates. However, HAMG may still explore a large number of unnecessary candidates because the graph neighborhood can be substantially larger than the true R𝑘NN result set. Proximity graphs such as HNSW [33] and NSG [14] have become the dominant paradigm for high-dimensional approximate 𝑘NN search. HAMG elegantly exploits the properties of the MRN graph, which is also a proximity graph. Since exact construction of an MRN graph is expensive, HAMG heuristically adapts the HNSW graph to better approximate the MRN structure. Although this heuristic adaptation weakens the theoretical guarantees of the original MRN graph, it remains effective in practice. There is a large body of work has studied high-dimensional 𝑘NN search from different perspectives, including distance computation optimization [11, 15, 55, 56], novel index structures [16, 44, 48], and search optimization techniques [9, 17, 25, 29, 31]. Since this paper focuses on R𝑘NN search, we omit detailed a discussion of these methods.

7

[9] Patrick Chen, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2023. FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search. In Proceedings of the ACM Web Conference 2023 (Austin, TX, USA) (WWW ’23). Association for Computing Machinery, New York, NY, USA, 3225–3235. https://doi.org/10.1145/3543507.3583318 [10] Qi-Zhu Dai, Zhong-Yang Xiong, Jiang Xie, Xiao-Xia Wang, Yu-Fang Zhang, and Jia-Xing Shang. 2019. A novel clustering algorithm based on the natural reverse nearest neighbor structure. Inf. Syst. 84, C (Sept. 2019), 1–16. https: //doi.org/10.1016/j.is.2019.04.001 [11] Liwei Deng, Penghao Chen, Ximu Zeng, Tianfu Wang, Yan Zhao, and Kai Zheng. 2024. Efficient Data-Aware Distance Comparison Operations for HighDimensional Approximate Nearest Neighbor Search. Proc. VLDB Endow. 18, 3 (Nov. 2024), 812–821. https://doi.org/10.14778/3712221.3712244 [12] Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web (Hyderabad, India) (WWW ’11). Association for Computing Machinery, New York, NY, USA, 577–586. https: //doi.org/10.1145/1963405.1963487 [13] Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2022), 4139–4150. https://doi.org/10.1109/TPAMI.2021.3067706 [14] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow. 12, 5 (Jan. 2019), 461–474. https://doi.org/10.14778/3303753.3303754 [15] Jianyang Gao and Cheng Long. 2023. High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations. Proc. ACM Manag. Data 1, 2, Article 137 (June 2023), 27 pages. https://doi.org/ 10.1145/3589282 [16] Yutong Gou, Jianyang Gao, Yuexuan Xu, and Cheng Long. 2025. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 1, Article 80 (Feb. 2025), 26 pages. https://doi.org/10.1145/3709730 [17] Hao Guo and Youyou Lu. 2026. Achieving Low-Latency Graph-Based Vector Search via Aligning Best-First Search Algorithm with SSD. ACM Trans. Storage 22, 2, Article 12 (March 2026), 30 pages. https://doi.org/10.1145/3793926 [18] Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Two (Barcelona, Catalonia, Spain) (IJCAI’11). AAAI Press, 1312–1317. [19] Reza Heydari-Gharaei, Rasoul Sharifi, Shima Kashef, and Hossein Nezamabadipour. 2025. A robust approach for outlier detection based on the ratio of number of reverse neighbors to neighbors. Pattern Anal. Appl. 28, 1 (Jan. 2025), 30. https://doi.org/10.1007/s10044-024-01372-y [20] Lihua Hu, Hongkai Liu, Jifu Zhang, and Aiqin Liu. 2022. KR-DBSCAN: A densitybased clustering algorithm based on reverse nearest neighbor and influence space. Expert Syst. Appl. 186, C (Dec. 2022), 8. https://doi.org/10.1016/j.eswa.2021.115763 [21] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. 604–613. [22] Piotr Indyk and Haike Xu. 2023. Worst-case performance of popular approximate nearest neighbor search implementations: guarantees and limitations. In Proceedings of the 37th International Conference on Neural Information Processing Systems (New Orleans, LA, USA) (NIPS ’23). Curran Associates Inc., Red Hook, NY, USA, Article 2891, 18 pages. [23] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc. https://proceedings.neurips. cc/paper_files/paper/2019/file/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Paper.pdf [24] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (Jan. 2011), 117–128. https://doi.org/10.1109/TPAMI.2010.57 [25] Sungjun Jung, Yongsang Park, Haeun Lee, Young H. Oh, and Jae W. Lee. 2025. Angular Distance-Guided Neighbor Selection for Graph-Based Approximate Nearest Neighbor Search. In Proceedings of the ACM on Web Conference 2025 (Sydney NSW, Australia) (WWW ’25). Association for Computing Machinery, New York, NY, USA, 4014–4023. https://doi.org/10.1145/3696410.3714870 [26] Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011. Searching in one billion vectors: Re-rank with source coding. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 861–864. https://doi.org/10.1109/ICASSP.2011.5946540 [27] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems 33 (2020), 9459–9474.

CONCLUSION

This paper studies approximate R𝑘NN search over highdimensional vectors. Motivated by the limitations of existing methods, we propose HRNN, a hybrid graph index that treats nearby neighbors as proxy points and materializes 𝑘NN-radius offline to avoid costly online computation. HRNN integrates a navigation graph, a ranked KNN graph, and reverse-neighbor lists, together with efficient index construction and append-only maintenance algorithms. Experiments on real-world datasets demonstrate that HRNN consistently outperforms existing methods in both efficiency and scalability while maintaining high search accuracy.

REFERENCES [1] Elke Achtert, Christian Böhm, Peer Kröger, Peter Kunath, Alexey Pryakhin, and Matthias Renz. 2006. Efficient reverse k-nearest neighbor search in arbitrary metric spaces. In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data (Chicago, IL, USA) (SIGMOD ’06). Association for Computing Machinery, New York, NY, USA, 515–526. https: //doi.org/10.1145/1142473.1142531 [2] Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. 2024. Self-RAG: Learning to Retrieve, Generate, and Critique through SelfReflection. In The Twelfth International Conference on Learning Representations. https://openreview.net/forum?id=hSyW5go0v8 [3] Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2023. Elpis: Graph-based similarity search for scalable data science. Proceedings of the VLDB Endowment 16, 6 (2023), 1548–1559. [4] Gautam Bhattacharya, Koushik Ghosh, and Ananda S. Chowdhury. 2015. Outlier detection using neighborhood rank difference. Pattern Recogn. Lett. 60, C (Aug. 2015), 24–31. https://doi.org/10.1016/j.patrec.2015.04.004 [5] Avory Bryant and Krzysztof Cios. 2018. RNN-DBSCAN: A Density-Based Clustering Algorithm Using Reverse Nearest Neighbor Density Estimates. IEEE Transactions on Knowledge and Data Engineering 30, 6 (2018), 1109–1121. https: //doi.org/10.1109/TKDE.2017.2787640 [6] Guillaume Casanova, Elias Englmeier, Michael E. Houle, Peer Kröger, Michael Nett, Erich Schubert, and Arthur Zimek. 2017. Dimensional testing for reverse k-nearest neighbor search. Proc. VLDB Endow. 10, 7 (March 2017), 769–780. https://doi.org/10.14778/3067421.3067426 [7] Muhammad Aamir Cheema, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2011. Influence zone: Efficiently processing reverse k nearest neighbors queries. In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering (ICDE ’11). IEEE Computer Society, USA, 577–588. https://doi.org/10.1109/ICDE. 2011.5767904 [8] Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X. Sean Wang. 2024. RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search. Proc. VLDB Endow. 17, 11 (July 2024), 2735–2749. https://doi.org/10.14778/3681954.3681959 15

[28] Binhong Li, Xiao Yan, and Shangqi Lu. 2026. Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 4, 1, Article 36 (April 2026), 24 pages. https://doi.org/10.1145/3786650 [29] Liang Li, Shufeng Gong, Yanan Yang, Yiduo Wang, and Jie Wu. 2026. I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration. https://doi.org/10.48550/arXiv.2602.21514 arXiv:2602.21514 [cs] [30] Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2021. HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search. Proceedings of the VLDB Endowment 15, 2 (2021), 246– 258. [31] Kejing Lu, Chuan Xiao, and Yoshiharu Ishikawa. 2024. Probabilistic routing for graph-based approximate nearest neighbor search. In Proceedings of the 41st International Conference on Machine Learning (Vienna, Austria) (ICML’24). JMLR.org, Article 1347, 19 pages. [32] Shangqi Lu and Yufei Tao. 2025. Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation. Proc. ACM Manag. Data 3, 5, Article 280 (Nov. 2025), 25 pages. https://doi.org/10.1145/3767716 [33] Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42, 4 (April 2020), 824–836. https://doi. org/10.1109/TPAMI.2018.2889473 [34] Brian McFee, Thierry Bertin-Mahieux, Daniel P.W. Ellis, and Gert R.G. Lanckriet. 2012. The million song dataset challenge. In Proceedings of the 21st International Conference on World Wide Web (Lyon, France) (WWW ’12 Companion). Association for Computing Machinery, New York, NY, USA, 909–916. https://doi.org/10.1145/2187980.2188222 [35] Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016. MS MARCO: A Human Generated MAchine Reading COmprehension Dataset.. In CoCo@NIPS (CEUR Workshop Proceedings), Tarek Richard Besold, Antoine Bordes, Artur S. d’Avila Garcez, and Greg Wayne (Eds.), Vol. 1773. CEUR-WS.org. http://dblp.uni-trier.de/db/conf/nips/coco2016. html#NguyenRSGTMD16 [36] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proc. ACM Manag. Data 1, 1, Article 54 (May 2023), 27 pages. https://doi.org/10. 1145/3588908 [37] Miloš Radovanović, Alexandros Nanopoulos, and Mirjana Ivanović. 2015. Reverse Nearest Neighbors in Unsupervised Distance-Based Outlier Detection. IEEE Transactions on Knowledge and Data Engineering 27, 5 (2015), 1369–1382. https: //doi.org/10.1109/TKDE.2014.2365790 [38] Payel Sadhukhan and Sarbani Palit. 2019. Reverse-nearest neighborhood based oversampling for imbalanced, multi-label datasets. Pattern Recogn. Lett. 125, C (July 2019), 813–820. https://doi.org/10.1016/j.patrec.2019.08.009 [39] Amit Singh, Hakan Ferhatosmanoglu, and Ali Şaman Tosun. 2003. High dimensional reverse nearest neighbor queries. In Proceedings of the Twelfth International Conference on Information and Knowledge Management (New Orleans, LA, USA) (CIKM ’03). Association for Computing Machinery, New York, NY, USA, 91–98. https://doi.org/10.1145/956863.956882 [40] Anbang Song, Ziqiang Yu, Wei Liu, Yating Xu, and Mingjin Tao. 2025. BRkNNlight: Batch Processing of Reverse k-Nearest Neighbor Queries for Moving Objects on Road Networks. In Proceedings of the 19th International Symposium on Spatial and Temporal Data (SSTD ’25). Association for Computing Machinery, New York, NY, USA, 80–89. https://doi.org/10.1145/3748777.3748791 [41] Yitong Song, Kai Wang, Bin Yao, Zhida Chen, Jiong Xie, and Feifei Li. 2024. Efficient Reverse 𝑘 Approximate Nearest Neighbor Search Over High-Dimensional Vectors. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). 4262–4274. https://doi.org/10.1109/ICDE60146.2024.00325 [42] Yufei Tao, Dimitris Papadias, and Xiang Lian. 2004. Reverse kNN search in arbitrary dimensionality. In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (VLDB ’04). VLDB Endowment, 744–755. [43] Yufei Tao, Dimitris Papadias, Xiang Lian, and Xiaokui Xiao. 2007. Multidimensional reverse kNN search. The VLDB Journal 16, 3 (July 2007), 293–316. https://doi.org/10.1007/s00778-005-0168-2 [44] Kento Tatsuno, Daisuke Miyashita, Taiga Ikeda, Kiyoshi Ishiyama, Kazunari Sumiyoshi, and Jun Deguchi. 2025. AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrieval. arXiv:2404.06004 [cs.IR]

https://arxiv.org/abs/2404.06004 [45] Hongya Wang, Wenlong Wu, Cong Luo, Aobei Bian, Chunguang Meng, Yishuo Wu, and Ji Sun. 2025. Boosting Accuracy and Efficiency for Vector Retrieval with Local Scaling Graph. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). 336–348. https://doi.org/10.1109/ICDE65448.2025.00032 [46] Mengzhao Wang, Haotian Wu, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, and Lu Chen. 2024. An Interactive Multi-Modal Query Answering System with Retrieval-Augmented Large Language Models. Proc. VLDB Endow. 17, 12 (Aug. 2024), 4333–4336. https://doi.org/10.14778/3685800.3685868 [47] Mengzhao Wang, Haotian Wu, Xiangyu Ke, Yunjun Gao, Yifan Zhu, and Wenchao Zhou. 2025. Accelerating Graph Indexing for ANNS on Modern CPUs. Proc. ACM Manag. Data 3, 3, Article 123 (June 2025), 29 pages. https://doi.org/10.1145/ 3725260 [48] Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-Efficient Disk Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment. Proc. ACM Manag. Data 2, 1, Article 14 (March 2024), 27 pages. https://doi.org/10.1145/3639269 [49] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc. VLDB Endow. 14, 11 (July 2021), 1964–1978. https://doi.org/10.14778/3476249.3476255 [50] Zeyu Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2023. Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions. IEEE Data Eng. Bull. 47, 3 (2023), 3–21. http://sites.computer.org/debull/A23sept/p3.pdf [51] Wei Wu, Fei Yang, Chee-Yong Chan, and Kian-Lee Tan. 2008. Finch: Evaluating reverse k-nearest-neighbor queries on location data. Proceedings of the VLDB Endowment 1, 1 (2008), 1056–1067. [52] Chenyi Xia, Wynne Hsu, and Mong Li Lee. 2005. ERkNN: efficient reverse knearest neighbors retrieval with local kNN-distance estimation. In Proceedings of the 14th ACM International Conference on Information and Knowledge Management (Bremen, Germany) (CIKM ’05). Association for Computing Machinery, New York, NY, USA, 533–540. https://doi.org/10.1145/1099554.1099697 [53] Jiadong Xie, Jeffrey Xu Yu, and Yingfan Liu. 2025. Graph based k-nearest neighbor search revisited. ACM Transactions on Database Systems 50, 4 (2025), 1–30. [54] Congyun Yang and King-Ip Lin. 2001. An index structure for efficient reverse nearest neighbor queries. In Proceedings 17th International Conference on Data Engineering. IEEE, 485–492. [55] Mingyu Yang, Liuchang Jing, Wentao Li, and Wei Wang. 2026. Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search. arXiv:2411.06158 [cs.DB] https://arxiv.org/abs/2411.06158 [56] Mingyu Yang, Wentao Li, Jiabao Jin, Xiaoyao Zhong, Xiangyu Wang, Zhitao Shen, Wei Jia, and Wei Wang. 2025. Effective and General Distance Computation for Approximate Nearest Neighbor Search. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). 1098–1110. https://doi.org/10.1109/ICDE65448.2025. 00087 [57] Shiyu Yang, Muhammad Aamir Cheema, Xuemin Lin, and Ying Zhang. 2014. SLICE: Reviving regions-based pruning for reverse k nearest neighbors queries. In 2014 IEEE 30th International Conference on Data Engineering. 760–771. https: //doi.org/10.1109/ICDE.2014.6816698 [58] Ori Yoran, Tomer Wolfson, Ori Ram, and Jonathan Berant. 2024. Making RetrievalAugmented Language Models Robust to Irrelevant Context. In The Twelfth International Conference on Learning Representations. https://openreview.net/forum? id=ZS4m74kZpH [59] Yue Yu, Wei Ping, Zihan Liu, Boxin Wang, Jiaxuan You, Chao Zhang, Mohammad Shoeybi, and Bryan Catanzaro. 2024. RankRAG: Unifying Context Ranking with Retrieval-Augmented Generation in LLMs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. https://openreview.net/ forum?id=S1fc92uemC [60] Aimin Zhang, Hualong Yu, Zhangjun Huan, Xibei Yang, Shang Zheng, and Shang Gao. 2022. SMOTE-RkNN: A hybrid re-sampling method based on SMOTE and reverse k-nearest neighbors. Information Sciences 595 (2022), 70–88. https: //doi.org/10.1016/j.ins.2022.02.038 [61] Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, et al. 2025. VSAG: An Optimized Search Framework for Graph-Based Approximate Nearest Neighbor Search. Proceedings of the VLDB Endowment 18, 12 (2025), 5017–5030.

16

Related documents

• String Diagrams for Process Mining#978502
• ZigZag Trie: A Novel Index for Contextual Queries#978503
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#978504
• Efficiently Linking Unstructured Data for Multi-step Reasoning#978505