HRNN: A Hybrid Graph Index for Approximate Reverse k k -Nearest Neighbor Search on High-Dimensional Vectors Wenxuan Xia, Mingyu Yang, Wentao Li, Wei Wang Abstract . Reverse k k -nearest neighbor (R k k NN) search returns all data points that regard a query vector as one of their k k -nearest neighbors ( k k NNs). Existing R k k NN methods typically follow a filter-and-verification framework : vectors near the query vector are first collected as candidates and then verified against their k k NN-radius (i.e., the distance to their k k -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 k k NN set, resulting in excessive candidate expansion overhead. Second, existing methods compute k k NN-radius online during verification, incurring substantial query-processing cost. To address these limitations, we propose 𝖧𝖱𝖭𝖭 {\mathsf{HRNN}} , a hybrid graph index for approximate R k k NN search. (1) Rather than directly treating nearby vectors as R k k NN candidates, 𝖧𝖱𝖭𝖭 {\mathsf{HRNN}} uses them as proxy points based on the assumption that a query’s R k k NN results can often be discovered through the R k k NN results of its nearby vectors. (2) To reduce verification cost, 𝖧𝖱𝖭𝖭 {\mathsf{HRNN}} materializes high-fidelity k k NN-radius offline, eliminating expensive online reconstruction while preserving accuracy. 𝖧𝖱𝖭𝖭 {\mathsf{HRNN}} combines a navigation graph, a ranked 𝖪𝖭𝖭 {\mathsf{KNN}} graph, and reverse-neighbor lists into a hybrid index that supports efficient proxy retrieval, candidate generation, and k k NN-radius access. We also develop efficient index construction and append-only maintenance algorithms. Extensive experiments show that 𝖧𝖱𝖭𝖭 {\mathsf{HRNN}} consistently outperforms existing methods, achieving up to one order of magnitude higher throughput. Moreover, 𝖧𝖱𝖭𝖭 {\mathsf{HRNN}} scales to datasets containing up to 10 million high-dimensional vectors while supporting efficient dynamic index maintenance. † † authors: . PVLDB Reference Format: PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † 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 info@vldb.org . 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 PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/gegeji/hrnn . 1. Introduction 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 ( 58 ; 2 ; 59 ) . Given a dataset D of vectors/data points, the k -nearest neighbors ( k NN) of a data point are the k points closest to it, where distance is typically measured using Euclidean distance. Conversely, the reverse k -nearest neighbors (R k NN) of a query point q consist of all data points in D that regard q as one of their k -nearest neighbors. Given a dataset D , the R k NN search problem aims to efficiently retrieve the R k NN set of a query vector q from D . The R k NN set of a query vector q naturally reflects its influence over the dataset D , since each vector in the R k NN set regards q as one of its k -nearest neighbors. Consequently, R k NN search has been widely used in applications that require influence analysis and reverse relationship discovery. For example, in spatial analytics, R k NN search can identify attractive facility locations by finding sites that appear among the k -nearest neighbors of a large number of customers ( 7 ) . In retrieval-augmented generation (RAG) systems, R k NN search can help identify influential knowledge chunks that are frequently referenced by many queries. More broadly, R k NN search has been extensively studied in machine learning tasks that rely on reverse influence relationships among data points, including density-based clustering ( 5 ; 20 ; 10 ) , outlier detection ( 37 ; 4 ; 19 ) , and class-imbalance sampling ( 60 ; 38 ) . To process the R k NN search for a query q , an intuitive approach is to first compute the k NN set of every point o in the dataset D and obtain its k NN-radius , i.e., the distance between o and its k -th nearest neighbor. Then, by definition, if the distance between q and point o\in D does not exceed the k NN radius of o , o is identified as an R k NN of q . However, this intuitive approach becomes prohibitively expensive when the dataset is large or the vector dimensionality is high. Although prior studies ( 40 ; 7 ) have explored spatial indexes such as R-trees to accelerate R k NN search, exact R k NN retrieval in high-dimensional vector spaces remains challenging. Thus, this paper focuses on approximate R k NN (i.e., AR k NN) search. Existing Solutions. Existing methods for AR k NN search generally follow a filter-and-verification framework . They first retrieve a superset of potential R k NN results for a query q as candidates, and then verify each candidate using a process similar to the intuitive approach described above. Early methods mainly rely on spatial partitioning ( 43 ; 42 ) 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 {\mathsf{SFT}} ( 39 ) , {\mathsf{RDT}} ( 6 ) , and the state-of-the-art {\mathsf{HAMG}} ( 41 ) , are based on the assumption that the R k 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- k^{\prime} nearest neighbors of the query vector in {\mathsf{SFT}} ( 39 ) and {\mathsf{RDT}} ( 6 ) , where k^{\prime}\mathrel{>\!\!>}k , or the k -hop neighbors in graph-based methods such as {\mathsf{HAMG}} ( 41 ) . They then verify whether each candidate belongs to the R k NN set of the query by comparing the query distance against the candidate’s k NN-radius. Figure 1 . Illustration of the inefficiency of existing methods. The radius of the circles centered at points (e.g., p_{1} and p_{2} ) in the dataset D denotes their k NN-radius. Given a query vector q , the goal is to retrieve its R k NN results ( p_{1} and p_{2} in this example, as we set k=1 ). Existing methods typically explore nearby neighbors, such as through top- k^{\prime} ( k^{\prime}\mathrel{>\!\!>}k ) nearest-neighbor search or k -hop graph expansion, and then verify whether the retrieved candidates are true R k NN results. However, to reach p_{2} , which has a large k 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. 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 k NN and nearby neighbors. Existing methods need to examine a large number of nearby neighbors to achieve high recall, because true R k NN results can be far away from the query vector in the embedding space (see Fig. 1 and Fig. 4 ). For example, a point o\in D may still regard query vector q as one of its k -nearest neighbors if o lies in a sparse region and therefore has a large k NN-radius. As a result, the query must search a large neighborhood region before reaching o , leading to excessive candidate expansion and unnecessary verification cost. This mismatch between R k 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 o belongs to the final R k NN result by comparing the distance between q and o against the k NN-radius of o . Specifically, if \delta(q,o) is no larger than the k NN-radius of o , then q is regarded as one of the k -nearest neighbors of o , and thus o is an R k NN of q . Yet, the k NN-radius of each candidate is typically computed online during query time ( 41 ; 6 ; 54 ) , as precomputing and storing these distances for all k values incurs prohibitive preprocessing costs or requires rebuilding the index. As a result, candidate verification introduces substantial computational overhead and becomes a major bottleneck in existing R k NN methods, as confirmed by our empirical studies. Table 1 . Comparison between {\mathsf{HRNN}} and existing R k NN methods. {\mathsf{HRNN}} (Ours) {\mathsf{HAMG}} {\mathsf{RDT}} {\mathsf{SFT}} Filter (Candidate Generation) Reverse-neighbor lists of proxies k -hop graph traversal Incremental k NN search One-shot k NN search Verification Pre-materialized k NN-radius Online computation Online computation Online computation Our Solution. To address the limitations of existing methods, we propose {\mathsf{HRNN}} , a H ybrid graph index for approximate R everse k - N earest N eighbor search. (1) To overcome the mismatch between R k NN results and nearby neighbors, rather than assuming that a query’s nearby neighbors directly contain its R k NN results, we make a different assumption: a query’s R k NN results can often be discovered through the R k NN results of its nearby neighbors. Based on this assumption, {\mathsf{HRNN}} first retrieves the query’s nearby neighbors (i.e., k NNs) as proxy points and then leverages their R k NN results to recover the query’s R k NN results. To support this process, each point maintains a reverse-neighbor list that records the points in D whose nearest-neighbor lists contain it, enabling efficient retrieval of its R k NN results for arbitrary k 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, {\mathsf{HRNN}} eliminates the expensive online computation of k NN-radius during query processing. Instead, it materializes k NN-radius information offline, enabling efficient candidate verification at query time. Achieving these goals is non-trivial, as the index must simultaneously support k NN retrieval for query vectors, reverse-neighbor-list access for proxy points, and fast k NN-radius lookup for arbitrary values of k . To this end, {\mathsf{HRNN}} integrates two complementary graph structures. First, it employs a navigation graph, such as {\mathsf{HNSW}} ( 33 ) , to retrieve the query’s nearest neighbors as proxy points. Second, it maintains a ranked {\mathsf{KNN}} graph ( 12 ) that stores nearest-neighbor relationships among data points. This graph provides direct access to pre-materialized k NN-radius for verification and serves as the basis for constructing reverse-neighbor lists, which enable efficient retrieval of proxy points’ R k NN results for candidate generation. By tightly integrating a navigation graph, a ranked {\mathsf{KNN}} graph, and reverse-neighbor lists into a unified index, {\mathsf{HRNN}} enables efficient R k NN query processing. We further develop efficient index construction and insertion-only maintenance algorithms. A comparison between {\mathsf{HRNN}} and existing methods is in Table 1 . Contributions. We summarize our main contributions as follows. Problem analysis (§ 3 ). We identify two key shortcomings of existing methods for high-dimensional AR k NN search. First, true R k NN results can be far away from the query vector in the embedding space, and thus the mismatch between R k NN results and nearby neighbors leads to excessive false positive candidates and unnecessary computation. Second, the k NN-radius of each candidate is computed online, which incurs huge overhead during the verification stage. Hybrid index design (§ 4 ). We propose {\mathsf{HRNN}} , a hybrid graph index for efficient AR k NN search. {\mathsf{HRNN}} integrates a navigation graph, a ranked {\mathsf{KNN}} graph, and reverse-neighbor lists derived from the ranked {\mathsf{KNN}} graph. The navigation graph is used to efficiently retrieve nearby proxy points, while the reverse-neighbor lists are used to recover the R k NN candidates of the query vector. In addition, the ranked {\mathsf{KNN}} graph materializes k NN-radius information for arbitrary values of k , enabling efficient candidate verification without expensive online k NN-radius computation. Index construction and maintenance (§ 4 ). We develop efficient algorithms for {\mathsf{HRNN}} index construction and maintenance. Specifically, we use the navigation graph as initialization seeds to improve the construction quality of the ranked {\mathsf{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 {\mathsf{HRNN}} improves the recall-throughput trade-off over strong R k NN baselines by up to one order of magnitude. Additional ablation, varying- k , and scalability experiments further validate the effectiveness of our {\mathsf{HRNN}} . Table 2 . Notation summary. Notation Description G_{{\mathsf{HNSW}}} {\mathsf{HNSW}} navigation graph G_{{\mathsf{KNN}}} Ranked {\mathsf{KNN}} graph G_{{\mathsf{KNN}}}[o] Ranked {\mathsf{KNN}} list of o , sorted by distance \mathbf{R}[o] Reverse-neighbor list of o r_{k}(o) k NN radius (distance to the k -th nearest neighbor) of o k Target parameter for k NN or R k NN search \mathbf{K} Number of stored neighbors per vertex in G_{{\mathsf{KNN}}} \Theta Rank threshold for reverse candidate generation m Number of proxy vectors retrieved from G_{{\mathsf{HNSW}}} \Theta_{u} Rank threshold used during insertion maintenance m_{u} Number of update proxies used during insertion maintenance 2. Preliminary We first formulate the approximate R k NN search problem, and then introduce the graph-based index that supports k NN retrieval. 2.1. Problem Definition We first introduce the definitions of k NN and R k NN, and then formally define the studied problem. Table 2 summarizes the commonly used notations in this paper. Definition 2.1 ( k -Nearest Neighbor ( k NN)). Given a dataset D of points in Euclidean space \mathbb{R}^{d} , a d -dimensional query vector q , and an integer k , the k NN set N_{k}(q) of q is a subset of D such that |N_{k}(q)|=k and \forall v\in N_{k}(q),\ \forall x\in D\setminus N_{k}(q),\ \delta(v,q)\leq\delta(x,q) . where \delta(v,q) denotes the Euclidean distance between v and q . Note that q may not belong to D . For each point o\in D , let N_{k}(o) denote its k NN in D , and let its k NN-radius be defined as r_{k}(o)=\delta(o,v) , where v\in N_{k}(o) is the k -th nearest neighbor of o . Definition 2.2 (Reverse k -Nearest Neighbor (R k NN)). Given a dataset D\subseteq\mathbb{R}^{d} , a d -dimensional query vector q , and an integer k , the R k NN set of q is defined as A_{k}(q)=\{o\in D\mid\delta(q,o)\leq r_{k}(o)\} . The R k NN set A_{k}(q) contains all points o\in D that regard q as one of their k nearest neighbors. Equivalently, the distance between q and o is no larger than the k NN-radius of point o . Since exact R k NN search is computationally expensive in high-dimensional spaces, existing methods typically trade accuracy for efficiency by returning approximate results. We therefore formally define the problem of approximate R k NN (AR k NN) search as follows. Definition 2.3 (Approximate Reverse k -Nearest Neighbor (AR k NN) Search). Given a dataset D , a query vector q , and an integer k , an AR k NN search returns a set \hat{A}_{k}(q)\subseteq D as an approximation to the exact R k NN result set A_{k}(q) . Its accuracy is evaluated against A_{k}(q) rather than by an \epsilon -relaxed membership predicate. Following ( 41 ) , we use Recall@ k to evaluate the accuracy of AR k NN results against the exact R k NN ground truth. Definition 2.4 (Recall@ k ). For a query q , let A_{k}(q) denote the exact R k NN result set and let \hat{A}_{k}(q) denote the approximate result set. The per-query Recall@ k is defined as \mathrm{Recall@}k(q)=\begin{cases}\frac{|A_{k}(q)\cap\hat{A}_{k}(q)|}{|A_{k}(q)|},&|A_{k}(q)|>0,\\ 1,&|A_{k}(q)|=0\text{ and }|\hat{A}_{k}(q)|=0,\\ 0,&|A_{k}(q)|=0\text{ and }|\hat{A}_{k}(q)|>0.\end{cases} For a query workload Q , Recall@ k is computed as the average of \mathrm{Recall@}k(q) over all q\in Q . Figure 2 . Illustrative examples of k NN and R k NN search. Example 2.5. Fig. 2 shows k NN and R k NN search. Let x_{1},\ldots,x_{4} be data points and q the query, with k=1 . In Fig. 2 (a), the nearest neighbor of q is x_{4} , and the (radius of the) circle centered at q denotes its k NN-radius. In Fig. 2 (b), the circles centered at x_{1},\ldots,x_{4} indicate their k NN-radius. Since q lies within the k NN-radius of x_{3} and x_{4} but outside those of x_{1} and x_{2} , the R k NN result set of q is \{x_{3},x_{4}\} . 2.2. Graph-Based k NN Search We briefly introduce graph-based methods for high-dimensional k NN search, which serve as the foundation of the studied AR k NN search problem. Among existing high-dimensional k NN methods, graph-based approaches ( 33 ; 14 ; 36 ; 13 ; 23 ; 49 ; 8 ; 12 ; 47 ; 50 ; 28 ; 22 ; 32 ; 18 ; 17 ; 61 ; 30 ) are particularly popular due to their state-of-the-art performance. These methods model the points in dataset D as vertices in a graph and connect nearby vertices through directed or undirected edges. As a result, k NN search for a query vector q becomes a graph traversal process over the constructed index. Ranked {\mathsf{KNN}} Graph. We first introduce the ranked {\mathsf{KNN}} graph, where \mathbf{K} is a user-defined parameter chosen to be sufficiently large to support k NN search for arbitrary k\leq\mathbf{K} . Definition 2.6 (Ranked {\mathsf{KNN}} Graph). Given a dataset D\subset\mathbb{R}^{d} and an integer \mathbf{K} , the ranked {\mathsf{KNN}} graph G_{{\mathsf{KNN}}}=(V,E) is a directed graph with vertex set V=D . Each vertex o\in V stores an ordered \mathbf{K} NN list of its \mathbf{K} nearest neighbors and their distances: G_{{\mathsf{KNN}}}[o]=\{(v_{1},\delta(o,v_{1})),\ldots,(v_{\mathbf{K}},\delta(o,v_{\mathbf{K}}))\} , where \delta(o,v_{1})\leq\ldots\leq\delta(o,v_{\mathbf{K}}) . A directed edge o\rightarrow v_{j} exists if v_{j} is the j -th nearest neighbor of o , i.e., G_{{\mathsf{KNN}}}[o,j]=v_{j} . For simplicity, we write G_{{\mathsf{KNN}}}[o,j]=v_{j} , although the actual entry is (v_{j},\delta(o,v_{j})) . The ranked G_{{\mathsf{KNN}}} captures nearest-neighbor relationships from the perspective of each point in D . Transposing these relationships yields reverse-neighbor lists, which record, for each vector, the points that regard it as one of their top- \mathbf{K} nearest neighbors. Consequently, the R k NN results of any dataset vector can be obtained directly from its reverse-neighbor list for any k\leq\mathbf{K} . Definition 2.7 (Reverse-Neighbor List). Given a ranked G_{{\mathsf{KNN}}} , the reverse-neighbor list of a vector o\in D , denoted by \mathbf{R}[o] , is defined as \mathbf{R}[o]=\{(v,j)\mid v\in D,\ G_{{\mathsf{KNN}}}[v,j]=o,\ 1\leq j\leq\mathbf{K}\} , where (v,j) indicates that o is the j -th nearest neighbor of v . 1 Input: Dataset D , integer \mathbf{K} Output: Ranked {\mathsf{KNN}} graph G_{{\mathsf{KNN}}} 2 Initialize G_{{\mathsf{KNN}}}[o] with \mathbf{K} random points for eacn o\in D ; 3 4 repeat 5 Create \mathbf{R}[o]\leftarrow\{x\mid o\in G_{{\mathsf{KNN}}}[x]\} for each o\in D ; 6 7 for each o\in D do N[o]\leftarrow G_{{\mathsf{KNN}}}[o]\cup\mathbf{R}[o] ; 8 9 for each o\in D do 10 for each neighbor pair (u,v) in N[o] do 11 Compute d=\delta(u,v) ; 12 Insert (v,d) into G_{{\mathsf{KNN}}}[u] if improved; 13 Insert (u,d) into G_{{\mathsf{KNN}}}[v] if improved; 14 until no neighbor list changes ; 15 Algorithm 1 Ranked {\mathsf{KNN}} Graph Construction Index construction. Exact construction of ranked {\mathsf{KNN}} graph requires O(|D|^{2}) distance computations, since the \mathbf{K} -nearest neighbors must be identified for every point in D . To improve efficiency, NNDescent ( 12 ) iteratively refines the \mathbf{K} NN list of each point based on the neighbors of its current neighbors. Algorithm 1 shows how to create the ranked {\mathsf{KNN}} graph using NNDescent. It first initializes the neighbor list G_{{\mathsf{KNN}}}[o] of each point o\in D with \mathbf{K} random points (Line 1). During each iteration, it constructs a reverse-neighbor list \mathbf{R}[o] for every point o , which contains all points that currently include o in their neighbor lists (Line 3). The forward and reverse neighbor lists are then merged to form the neighbor set N[o] (Line 4). For each neighbor pair (u,v) in N[o] (Lines 5–6), the algorithm computes their distance \delta(u,v) and attempts to insert (v,d) into G_{{\mathsf{KNN}}}[u] and (u,d) into G_{{\mathsf{KNN}}}[v] if the new neighbor improves the current ranked neighbor list (Lines 7–9). Here, we say that (v,d) updates G_{{\mathsf{KNN}}}[u] if the distance d=\delta(u,v) is smaller than the distance between u and at least one neighbor currently stored in G_{{\mathsf{KNN}}}[u] . 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 {\mathsf{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 ( {\mathsf{HNSW}} ) graph ( 33 ) , have been proposed. Definition 2.8 ( {\mathsf{HNSW}} Graph). Given a dataset D\subset\mathbb{R}^{d} , an {\mathsf{HNSW}} graph is an L -layer directed proximity graph G_{{\mathsf{HNSW}}}=\{G^{(0)},G^{(1)},\ldots,G^{(L)}\} , where each layer G^{(\ell)}=(V^{(\ell)},E^{(\ell)}) is defined over a subset V^{(\ell)}\subseteq D , satisfying V^{(L)}\subseteq V^{(L-1)}\subseteq\cdots\subseteq V^{(0)}=D . Each point o\in D is assigned a maximum level \lambda(o) and appears in all layers G^{(0)},\ldots,G^{(\lambda(o))} . At each layer \ell\leq\lambda(o) , point o maintains a bounded sized neighbor list G^{(\ell)}[o]=\{v_{1},\ldots,v_{M}\} , where each v_{i}\in V^{(\ell)} is selected using proximity-based pruning heuristics. A directed edge o\rightarrow v_{i} exists in layer G^{(\ell)} if v_{i}\in G^{(\ell)}[o] . 1 Input: Graph G , query vector q , target number of results k , entry point ep , beam width ef Output: Candidate set W[q] of size k 2 Initialize min-heap Q\leftarrow\{ep\} ordered by \delta(q,\cdot) ; 3 Initialize max-heap W[q]\leftarrow\{ep\} ordered by \delta(q,\cdot) ; 4 Mark ep as visited; 5 6 while Q\neq\emptyset do 7 Extract the closest vertex v from Q ; 8 Let u be the farthest vertex in W[q] ; 9 10 if \delta(q,v)>\delta(q,u) then break ; 11 12 for each unvisited neighbor o\in G[v] do 13 Mark o as visited; 14 15 if |W[q]|k then 19 Remove the farthest vertex from W[q] ; 20 if |Q|>ef then 21 Remove the farthest vertex from Q ; 22 23 return W[q] ; 24 Algorithm 2 Graph-Search (G,q,k,ep,ef) Search on the {\mathsf{HNSW}} graph. Given a query q , an {\mathsf{HNSW}} graph G_{{\mathsf{HNSW}}} , the target result size k , and a beam width ef , search on the {\mathsf{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 ef=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 G^{(0)} , the algorithm performs beam search with a larger beam width ef>1 to retrieve the final k NN result for the query vector q . The search within each layer G^{(\ell)} follows Algorithm 2 . Given the current entry point ep , the algorithm initializes a candidate heap Q and a result heap W[q] with ep (Lines 1–2), and marks it as visited (Line 3). It then repeatedly extracts the closest vertex v from Q (Line 5) and compares it with the farthest vertex u in W[q] (Line 6). If v is farther from q than u , the search stops because no remaining candidate can improve the current result (Line 7). Otherwise, the algorithm scans each unvisited neighbor o\in G^{(\ell)}[v] (Line 8), marks it as visited (Line 9), and inserts it into both Q and W[q] . if W[q] has fewer than k vertices or o is closer to q than the current farthest candidate (Lines 10–11). If W[q] or Q exceeds their size limits, the farthest vertex is removed (Line 12–15). The search returns W[q] as the result (Line 16). Figure 3 . Illustration of an {\mathsf{HNSW}} graph and the graph search process. Example 2.9. Fig. 3 (a) illustrates an {\mathsf{HNSW}} graph with three layers, where G^{(2)} is the top layer and G^{(0)} is the bottom layer. Given a query vector q , the top-down routing phase starts from the global entry point ep=x_{4} and performs greedy search ( ef=1 ) on each layer. The search progressively descends through the hierarchy until reaching the bottom layer, where x_{7} is identified as the entry point. Fig. 3 (b) illustrates the bottom-layer beam search ( ef=2 ). Starting from x_{7} , the search visits x_{5} and inserts x_{2} and x_{9} into the candidate queue. Since \delta(q,x_{2})<\delta(q,x_{9}) , x_{2} is expanded first, followed by x_{9} , which discovers x_{1} . The final 2NN result is W[q]={x_{1},x_{2}} (shaded in purple). 3. Problem Analysis We summarize existing methods for R k 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 k NN search to refer to approximate R k NN search throughout the remainder of the paper unless otherwise specified. 3.1. Existing Solutions The main challenge in answering the R k NN search problem lies in two aspects. First, unlike k NN search, where the result vectors are directly close to the query vector q , the vectors in the R k NN set do not necessarily have explicit proximity relationships with q . Specifically, R k NN search is defined from the perspective of dataset points o\in D : we need to determine whether q belongs to the k NN set of points o by checking the k NN-radius of o . Second, unlike k NN search, which always returns exactly k vectors, the number of reverse k NN results for a query vector is unknown in advance. To process the R k NN search problem for a query vector q over dataset D , an intuitive approach is to directly follow the definition of R k NN. Specifically, the algorithm scans all points o\in D and checks whether the distance \delta(q,o) is no larger than the k NN-radius r_{k}(o) of o , where r_{k}(o) is defined as the distance from o to its k -th nearest neighbor. If so, o is included in the R k NN set of q . 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 D , these methods first reduce the search space to a candidate set C\subseteq D , and then verify whether each candidate point belongs to the R k NN result set of the query vector q . To obtain a compact candidate set C , existing methods commonly assume that data points close to q are more likely to regard q as one of their k nearest neighbors, and thus are more likely to belong to the R k NN result set of q . Based on this assumption, methods such as {\mathsf{SFT}} ( 39 ) and {\mathsf{RDT}} ( 6 ) first perform nearest-neighbor search and then examine nearby neighbors as candidates until a stopping condition is satisfied. GIST ( d\!=\!960 ) SIFT ( d\!=\!128 ) MSMARCO ( d\!=\!1024 ) 10^{0} 10^{2} 10^{4} 10^{6} 0 0.5 1 Rank of farthest R k NN groundtruth result among q ’s neighbors CDF Figure 4. The cumulative distribution function (CDF) of the ranks of points in the R k NN result sets of query vectors. A higher rank indicates that more nearby neighbors must be explored before the exact R k NN ( k=10 ) results can be retrieved. The State-of-the-Art. More recently, {\mathsf{HAMG}} ( 41 ) was proposed following the same intuition. A key insight of {\mathsf{HAMG}} is that, on the Monotonic Relative Neighborhood ( {\mathsf{MRN}} ) graph ( 33 ; 14 ; 36 ; 13 ; 23 ; 49 ; 8 ; 12 ; 47 ; 50 ; 28 ; 22 ; 32 ; 18 ; 45 ; 30 ; 3 ; 53 ) , the R k NN results of a query vector q are guaranteed to lie within the k -hop neighborhood of q . Based on this property, {\mathsf{HAMG}} treats these nearby graph neighbors as the candidate set C . Specifically, {\mathsf{HAMG}} adopts the hierarchical structure of the ( {\mathsf{HNSW}} ) graph in Definition 2.8 , while modifying the bottom layer G^{(0)} to better approximate the {\mathsf{MRN}} graph structure. Using this adapted ( {\mathsf{HNSW}} ) graph, {\mathsf{HAMG}} retrieves the k -hop neighbors of q as candidates and then verifies whether \delta(q,o)\leq r_{k}(o) for each candidate o\in C to determine if o belongs to the R k NN set of q . More details can be found in ( 41 ) . 3.2. Limitation Analysis Existing methods avoid scanning the entire dataset D to retrieve the R k NN results of a query vector q . Yet, they still suffer from two major limitations that reduce their efficiency on large datasets. SIFT MSMARCO SFT RDT HAMG HRNN 10^{0} 10^{1} 10^{2} 10^{3} 18 32 120 2.1 57 127 471 4.1 (a) SFT RDT HAMG HRNN 10^{-1} 10^{1} 10^{3} 322 347 550 0.14 1186 1277 3542 0.38 (b) Figure 5 . Comparison of query performance for approximate R k NN search with k=10 at Recall@10 = 0.99. (a) shows the total query latency of {\mathsf{HRNN}} and the baselines ( {\mathsf{SFT}} , {\mathsf{RDT}} , and {\mathsf{HAMG}} ). (b) reports the per-candidate verification cost of {\mathsf{HRNN}} and the baselines. Limitation 1: The mismatch between R k NN and nearby neighbors. Existing methods rely on the assumption that nearby neighbors of q (e.g., nearest neighbors in {\mathsf{SFT}} and {\mathsf{RDT}} , or graph neighbors within k hops in {\mathsf{HAMG}} ) contain all R k 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 o\in D has a large k NN-radius, the query vector q may still belong to the k NN set of o even if o is far away from q . Consequently, the search algorithm must traverse a large number of nearby neighbors before reaching o . Even for the state-of-the-art {\mathsf{HAMG}} , the number of k -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 k=10 for R k NN search. For each query q , we compute its exact R k NN result set. For every object in the result set, we measure its rank in the nearest-neighbor ordering of q , where the closest neighbor has rank 1 and the farthest point has rank |D| . 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 k NN results. For example, on SIFT, more than 50\% of queries require scanning over 10^{3} nearby neighbors to retrieve all R k NN results. More critically, some queries require exploring an extremely large neighborhood region. On GIST, certain queries need to scan more than 10^{6} nearby neighbors before all R k NN results can be identified. These observations indicate that relying solely on nearby neighbors is inefficient for R k NN search. Limitation 2: High Verification Cost. The first limitation implies that existing R k NN methods often explore a large number of unnecessary neighbors during the filter stage, producing a candidate set C that is substantially larger than the true R k NN result set. Then, for each candidate vector o\in C , the algorithm must determine whether \delta(o,q)\leq r_{k}(o) . If the condition does not hold, then q is not among the k nearest neighbors of o , and o is discarded; otherwise, o is reported as an R k NN result. Consequently, efficient computation of the k NN-radius r_{k}(o) of o is critical to R k NN search performance. Obtaining this value requires issuing a k NN query centered at o , as precomputing k NN-radius and supporting queries for arbitrary k values necessitate either prohibitive preprocessing cost or even complete index reconstruction in existing indexes ( 39 ; 6 ; 41 ; 54 ) . Besides, since the candidate set C is not known in advance and can be very large in practice, existing methods incur substantial overhead by computing k NN-radius online during query processing. To quantify this limitation, we conduct experiments on the real-world SIFT and MSMARCO datasets. We compare the runtime of approximate R k NN search across {\mathsf{HRNN}} and the baseline methods ( {\mathsf{SFT}} , {\mathsf{RDT}} , and {\mathsf{HAMG}} ), with the results reported in Fig. 5 . As shown in Fig. 5 (a), {\mathsf{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 k NN-radius online. These results demonstrate that online k NN-radius computation is a major bottleneck for existing R k NN methods. 4. The Proposed Method 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. Index Structure We now present the key ideas for addressing the two limitations of existing R k NN methods. Idea 1. To address Limitation 1, we revisit the relationship between k NN and R k 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 k NN search. However, as shown in our analysis, nearby neighbors are often not true R k NN results. Instead, we make a different assumption: a query’s R k NN results can often be discovered through the R k NN results of its nearby neighbors. This intuition is empirically validated in Fig. 6 . m\!=\!1 m\!=\!5 m\!=\!10 m\!=\!20 10^{0} 10^{2} 10^{4} 10^{6} 0 0.5 1 \Theta\!=\!500 Proxy rank \rho_{m}(q,x) CDF (a) 10^{0} 10^{2} 10^{4} 10^{6} 0 0.5 1 \Theta\!=\!500 Proxy rank \rho_{m}(q,x) (b) Figure 6. To validate our assumption, we evaluate the proxy ranks of exact R k NN results on the SIFT and MSMARCO datasets. For each query vector q , its top- m nearest neighbors are used as proxies ( m\in\{1,5,10,20\} ). Consider an exact R k NN result x ( k=10 ) of q . We define the proxy rank of x as the smallest rank position of any proxy of q in x ’s ranked \mathbf{K} NN list. By Definition 2.7 , if a proxy appears at rank r in x ’s ranked \mathbf{K} NN list, then x appears in the proxy’s reverse-neighbor list and can be discovered after scanning its reverse-neighbor list. Therefore, a small proxy rank of r indicates that x 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 m increases. In particular, about 50% of the R k 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. This assumption follows from spatial proximity: as q and its nearby neighbors lie close to each other, they are likely to fall within the k NN radius of the same point x . Thus, if x is an R k NN of q ’s nearby neighbors, it is also likely to appear in the R k NN sets of q . Based on this intuition, we first retrieve a set of nearby vectors as proxies . Rather than treating these proxies as R k NN candidates, we leverage their reverse-neighbor lists, which provide their R k NN results for arbitrary k , to generate candidates for the query. This design avoids excessive neighborhood expansion while keeping high recall. Idea 2. To address Limitation 2, we eliminate the expensive online computation of k NN-radius during verification. Recall that the k NN-radius of a vector o\in D is simply the distance between o and its k -th nearest neighbor. Thus, if we materialize a ranked neighbor list for each vector and store the corresponding distances in ascending order, the k NN-radius for any value of k can be retrieved directly through a lookup. This transforms verification from an expensive online search into a lightweight index-access operation. 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 k NN candidates for the query, and (3) maintaining ranked neighbor lists for all points in the dataset so that k NN-radius can be accessed efficiently during verification. Designing a single index that satisfies all these requirements is non-trivial. For example, the {\mathsf{HNSW}} graph is highly effective for nearest-neighbor retrieval but does not maintain ranked neighbor lists. In contrast, a ranked {\mathsf{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 k NN sets of data vectors. To address these challenges, we propose {\mathsf{HRNN}} , a hybrid index that integrates an {\mathsf{HNSW}} graph, a ranked {\mathsf{KNN}} graph, and reverse-neighbor lists. Definition 4.1 ( {\mathsf{HRNN}} Index). Given a dataset D and a user-defined parameter \mathbf{K} , the {\mathsf{HRNN}} index is defined as \mathcal{I}=(G_{{\mathsf{HNSW}}},G_{{\mathsf{KNN}}},\mathbf{R}) , where: (1) G_{{\mathsf{HNSW}}} is an {\mathsf{HNSW}} graph constructed over D (Definition 2.8 ); (2) G_{{\mathsf{KNN}}} is a ranked {\mathsf{KNN}} graph constructed over D with parameter \mathbf{K} (Definition 2.6 ); (3) \mathbf{R} is the reverse-neighbor lists derived from G_{{\mathsf{KNN}}} . For each vector o\in D , its reverse-neighbor list \mathbf{R}[o] stores all pairs (v,j) such that o is the j -th nearest neighbor of v in G_{{\mathsf{KNN}}} (Definition 2.7 ). Figure 7 . An example of the {\mathsf{HRNN}} index structure. Example 4.2. Fig. 7 shows the components of {\mathsf{HRNN}} . Fig. 7 (a) shows the {\mathsf{HNSW}} graph. Fig. 7 (b) presents the ranked {\mathsf{KNN}} graph, where each node o maintains a list of \mathbf{K} -nearest neighbors ( \mathbf{K}=2 ), and each entry is denoted as (v_{i},\delta(o,v_{i})) . For instance, x_{2} is the 1NN of x_{3} with \delta(x_{3},x_{2})=5 . Fig. 7 (c) shows the reverse-neighbor lists derived from G_{{\mathsf{KNN}}} . For example, since x_{3} is the 1NN of x_{2} and the 2NN of x_{1} , its reverse-neighbor list is \mathbf{R}(x_{3})=\{(x_{2},1),(x_{1},2)\} , which records these reverse-neighbor relationships. Theorem 4.3. The {\mathsf{HRNN}} index requires O(|D|\cdot M\cdot L+|D|\cdot\mathbf{K}) space, where L is the number of {\mathsf{HNSW}} layers, M is the maximum degree of the {\mathsf{HNSW}} graph, and \mathbf{K} is the number of ranked neighbors materialized per point. Proof. The {\mathsf{HRNN}} index consists of three components. First, the {\mathsf{HNSW}} graph stores at most M outgoing neighbors for each vector at each layer. Since there are at most |D| vectors and L layers, the space required by the {\mathsf{HNSW}} graph is bounded by O(|D|\cdot M\cdot L) . Second, the ranked {\mathsf{KNN}} graph stores \mathbf{K} ranked neighbors for each vector, requiring O(|D|\cdot\mathbf{K}) space. Third, the reverse-neighbor lists are obtained by transposing the ranked {\mathsf{KNN}} graph. Each ranked neighbor entry generates exactly one reverse posting, yielding |D|\cdot\mathbf{K} reverse postings in total and therefore requiring O(|D|\cdot\mathbf{K}) space. Summing the three components gives O(|D|\cdot M\cdot L+2|D|\cdot\mathbf{K})=O(|D|\cdot M\cdot L+|D|\cdot\mathbf{K}) . ∎ 4.2. Query Processing We now describe how to answer an approximate R k NN query for a query vector q using the proposed {\mathsf{HRNN}} index \mathcal{I}=(G_{{\mathsf{HNSW}}},G_{{\mathsf{KNN}}},\mathbf{R}) . If the query vector q were part of the indexed dataset D , its reverse-neighbor list \mathbf{R}[q] would directly reveal the points whose neighborhoods contain q . However, in practice, query vectors are typically not part of the indexed dataset. To address this issue, {\mathsf{HRNN}} first retrieves a set of nearby points as proxies and uses their reverse-neighbor lists to approximate the unavailable reverse-neighborhood information of q . Filter. Let N_{m}(q)=\{b_{1},\ldots,b_{m}\} denote the approximate m -nearest neighbors of q returned by the {\mathsf{HNSW}} graph. Rather than treating these points as R k NN candidates, {\mathsf{HRNN}} uses them to discover candidate points. To avoid scanning excessively large reverse-neighbor lists \mathbf{R}[b] of the proxy point b\in N_{m}(q) , we introduce a rank threshold \Theta and only consider vectors whose ranks do not exceed \Theta . This design is based on the intuition that if the rank of an object v with respect to a proxy b exceeds \Theta , then b —and thus the query—is unlikely to be within the top- \Theta nearest neighbors of v . Hence, v can be safely pruned, as it is unlikely to be an R \Theta NN of q . Formally, the candidate set of query q is defined as (1) C_{m,\Theta}(q)=\bigcup_{b\in N_{m}(q)}\{v\mid(v,j)\in\mathbf{R}[b],\ j\leq\Theta\}. A larger \Theta increases candidate coverage and potentially improves recall, but incurs higher candidate-generation and verification costs. Note that \mathbf{K} is the number of neighbors materialized in a ranked {\mathsf{KNN}} graph, while \Theta\leq\mathbf{K} is a query-time parameter controlling the number of entries scanned from each reverse-neighbor list. Verification. After candidate generation, {\mathsf{HRNN}} verifies whether each candidate o\in C_{m,\Theta}(q) belongs to the final R k NN result set of q . Existing methods typically compute the k NN-radius of each candidate online, which incurs substantial overhead. In contrast, {\mathsf{HRNN}} leverages the pre-materialized ranked {\mathsf{KNN}} graph G_{{\mathsf{KNN}}} . Since the graph stores the top- \mathbf{K} nearest neighbors of every vertex and \mathbf{K}\geq k , the k -th nearest neighbor of o can be directly retrieved from G_{{\mathsf{KNN}}}[o] . Let v_{k} denote this neighbor. The corresponding distance \hat{r}_{k}(o)=\delta(o,v_{k}) serves as an estimate of the k NN-radius of o . Using this pre-materialized radius, a candidate o is accepted if \delta(q,o)\leq\hat{r}_{k}(o) . This verification process reduces candidate validation to a single distance comparison. Input: Index \mathcal{I}=(G_{{\mathsf{HNSW}}},G_{{\mathsf{KNN}}},\mathbf{R}) , query vector q , target parameter k , proxy size m , rank threshold \Theta , {\mathsf{HNSW}} search parameters ep and ef_{s} Output: AR k NN result set R 1 R\leftarrow\emptyset,\ C\leftarrow\emptyset ; 2 3 N_{m}(q)\leftarrow\textsc{Graph-Search}(G_{{\mathsf{HNSW}}},q,m,ep,ef_{s}) ; 4 5 for b\in N_{m}(q) do 6 for (v,j)\in\mathbf{R}(b) in ascending order of j do 7 if j>\Theta then break; 8 C\leftarrow C\cup\{v\} ; 9 10 for o\in C do 11 v_{k}\leftarrow G_{{\mathsf{KNN}}}[o,k] ; 12 \hat{r}_{k}(o)\leftarrow\delta(o,v_{k}) ; 13 if \delta(q,o)\leq\hat{r}_{k}(o) then R\leftarrow R\cup\{o\} ; 14 return R ; 15 Algorithm 3 Approximate R k NN Search Algorithm. Algorithm 3 presents the procedure for answering an approximate R k NN query for a query vector q using the hybrid index \mathcal{I}=(G_{{\mathsf{HNSW}}},G_{{\mathsf{KNN}}},\mathbf{R}) . The algorithm first performs an approximate m -nearest-neighbor search on G_{{\mathsf{HNSW}}} to retrieve a set of proxy vertices N_{m}(q) that are close to q (Line 2). The details of the graph search procedure are provided in Algorithm 2 . For each proxy point b\in N_{m}(q) , the algorithm scans its reverse-neighbor list \mathbf{R}(b) in ascending rank order (Lines 3–4). Only vertices whose ranks do not exceed the threshold \Theta are inserted into the candidate set C (Lines 5–6). This proxy-guided reverse lookup generates candidate R k NN results without expensive neighborhood expansion. The algorithm then verifies each candidate o\in C (Line 7). Specifically, it retrieves the k -th nearest neighbor v_{k} of o from G_{{\mathsf{KNN}}} and obtains the corresponding estimated k NN-radius \hat{r}_{k}(o)=\delta(o,v_{k}) (Lines 8–9). A candidate is accepted if \delta(q,o)\leq\hat{r}_{k}(o) (Line 10). All verified candidates are added to the result set R , which is returned as the final R k NN result (Line 11). Figure 8 . An example of the {\mathsf{HRNN}} search process. Example 4.4. Fig. 8 illustrates {\mathsf{HRNN}} query processing for a query vector q , with m=2 and \Theta=1 . The search first traverses G_{{\mathsf{HNSW}}} and retrieves x_{2} and x_{3} as proxy vertices, as shown in Fig. 8 (a). As illustrated in Fig. 8 (b), {\mathsf{HRNN}} then scans the reverse-neighbor lists of the proxies in ascending rank order and inserts vertices whose rank does not exceed \Theta into the candidate set C . In this example, x_{1} , x_{2} , x_{3} , and x_{6} are added to C . Finally, each candidate is verified by checking whether q falls within its k NN-radius, which is obtained directly from G_{{\mathsf{KNN}}} . Candidates satisfying this condition (e.g., x_{3} ) are returned as R k NN results. Theorem 4.5. Given a query vector q , Algorithm 3 answers the R k NN query in expected time O\!\left(\log|D|+m+s(q)+d\cdot u(q)\right) , where m is the proxy size, s(q) is the number of scanned reverse-neighbor entries, and u(q) is the number of distinct candidates after deduplication (i.e., the size of C_{m,\Theta}(q) in Equation 1). Proof. Proxy retrieval over the {\mathsf{HNSW}} graph requires O(\log|D|+m) expected time. Candidate generation scans s(q) reverse-neighbor entries and therefore takes O(s(q)) time. After deduplication, the algorithm verifies u(q) candidates. Each verification consists of one exact distance computation and one constant-time radius lookup, requiring O(d) time. Thus, verification costs O(d\cdot u(q)) . Summing the three terms yields the stated bound. ∎ 4.3. Index Construction Constructing the {\mathsf{HRNN}} index \mathcal{I}=(G_{{\mathsf{HNSW}}},G_{{\mathsf{KNN}}},\mathbf{R}) is challenging because it consists of three coupled structures: the {\mathsf{HNSW}} graph, the ranked {\mathsf{KNN}} graph, and the reverse-neighbor lists. A straightforward approach is to construct them independently, but this would incur redundant neighborhood exploration and repeated nearest-neighbor computations. To avoid this overhead, {\mathsf{HRNN}} adopts a unified construction pipeline. It first builds the {\mathsf{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 {\mathsf{KNN}} list. {\mathsf{HRNN}} then applies NNDescent to refine these initial neighborhoods and construct a high-quality ranked {\mathsf{KNN}} graph. Compared with random initialization, this strategy improves convergence and reduces construction cost. Finally, the reverse-neighbor lists are derived by transposing the ranked {\mathsf{KNN}} graph: if a vector u is the j -th nearest neighbor of a vector v , the pair (v,j) is inserted into the reverse-neighbor list of u . In this way, {\mathsf{HRNN}} constructs all three index structures efficiently while maximizing the reuse of neighborhood information across different index views. Input: Dataset D\subset\mathbb{R}^{d} ; {\mathsf{HNSW}} parameters M , ef_{c} , and m_{L} ; ranked KNN size \mathbf{K} ; NNDescent iterations T 1 Output: Index \mathcal{I}=(G_{{\mathsf{HNSW}}},G_{{\mathsf{KNN}}},\mathbf{R}) 2 // Phase 1: Build the {\mathsf{HNSW}} graph (G_{{\mathsf{HNSW}}},W)\leftarrow\textsc{Build-HNSW}(D,M,ef_{c},m_{L}) ; 3 4 // Phase 2: Construct the ranked KNN graph Initialize G_{{\mathsf{KNN}}}[o] using W[o] for each o\in D ; 5 6 Execute Lines 2–11 of Algorithm 1 to build G_{{\mathsf{KNN}}} ; 7 8 // Phase 3: Construct reverse-neighbor lists Initialize \mathbf{R}(o)\leftarrow\emptyset for all o\in D ; 9 10 for each o\in D do 11 for j\leftarrow 1 to \mathbf{K} do 12 v\leftarrow G_{{\mathsf{KNN}}}[o,j] ; 13 Append (o,j) to \mathbf{R}(v) ; 14 15 for each o\in D do 16 Sort \mathbf{R}(o) in ascending order of rank j ; 17 18 return \mathcal{I}=(G_{{\mathsf{HNSW}}},G_{{\mathsf{KNN}}},\mathbf{R}) ; 19 Algorithm 4 {\mathsf{HRNN}} Index Construction Algorithm. Algorithm 4 constructs the {\mathsf{HRNN}} index \mathcal{I}=(G_{{\mathsf{HNSW}}},G_{{\mathsf{KNN}}},\mathbf{R}) in three phases. First, {\mathsf{HRNN}} builds the {\mathsf{HNSW}} graph G_{{\mathsf{HNSW}}} over the dataset D (Line 1). During {\mathsf{HNSW}} construction, each point is inserted incrementally. For a newly inserted point o , {\mathsf{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 o to existing vertices in different {\mathsf{HNSW}} layers. Meanwhile, {\mathsf{HRNN}} records the bottom-layer search results as W[o] , which provides high-quality initial neighbor candidates for constructing the ranked {\mathsf{KNN}} graph. Second, {\mathsf{HRNN}} constructs the ranked {\mathsf{KNN}} graph G_{{\mathsf{KNN}}} (Lines 2–3). Instead of randomly initializing the neighbor list of each vertex, {\mathsf{HRNN}} initializes G_{{\mathsf{KNN}}}[o] using W[o] , i.e., the candidate neighbors obtained during {\mathsf{HNSW}} construction. Then, Lines 2–11 of Algorithm 1 are executed to refine these initial lists via NNDescent to build a G_{{\mathsf{KNN}}} . Third, {\mathsf{HRNN}} builds the reverse-neighbor lists \mathbf{R} from G_{{\mathsf{KNN}}} (Lines 4). For each vertex o and each rank position j (Line 5–6), the algorithm obtains the j -th nearest neighbor v=G_{{\mathsf{KNN}}}[o,j] (Line 7) and appends (o,j) to \mathbf{R}(v) (Line 8). Finally, each reverse-neighbor list is sorted by rank j (Line 9–10). Figure 9 . An example of {\mathsf{HRNN}} index construction. Example 4.6. Fig. 9 illustrates the construction process of the {\mathsf{HRNN}} index. Fig. 9 (a) shows the search performed when inserting a new point x_{6} into G_{{\mathsf{HNSW}}} , and x_{6} is connected to x_{2} after pruning the search results. Other points are inserted similarly. The search result [x_{2},x_{3}] is recorded and used to initialize the ranked {\mathsf{KNN}} graph with \mathbf{K}=2 , as shown in Fig. 9 (b). Fig. 9 (c) shows how NNDescent refines the ranked {\mathsf{KNN}} graph. For example, in x_{6} ’s neighbor list, the initial 2NN x_{3} is replaced by the closer neighbor x_{7} . Finally, Fig. 9 (d) constructs the reverse-neighbor lists by scanning the refined ranked {\mathsf{KNN}} graph. For instance, since x_{2} appears as the 1NN of x_{1} , x_{3} , and x_{6} , its reverse-neighbor list is \mathbf{R}(x_{2})=[(x_{1},1),(x_{3},1),(x_{6},1)] . Theorem 4.7. Algorithm 4 constructs the {\mathsf{HRNN}} index in expected time O\left(|D|\cdot\log|D|+T\cdot|D|\cdot\mathbf{K}^{2}\cdot d+|D|\cdot\mathbf{K}\right) , where d is the vector dimension, \mathbf{K} is the ranked neighbor-list size, and T is the number of NNDescent refinement iterations. Proof. Algorithm 4 consists of three phases. First, the algorithm builds the {\mathsf{HNSW}} graph over D . {\mathsf{HNSW}} inserts vectors incrementally. For each inserted vector, it performs graph search to locate candidate neighbors and then selects at most M neighbors for graph construction. Following the standard logarithmic search behavior of {\mathsf{HNSW}} , the expected cost of inserting one vector is O(\log|D|) . Therefore, inserting all |D| vectors costs O(|D|\cdot\log|D|) . During this phase, {\mathsf{HNSW}} also records the bottom-layer search results as initialization seeds for the ranked {\mathsf{KNN}} graph. This recording is performed during {\mathsf{HNSW}} construction and does not change the asymptotic cost. Second, {\mathsf{HRNN}} constructs the ranked {\mathsf{KNN}} graph. Each vector maintains a ranked list of \mathbf{K} neighbors. The initial lists are obtained from the {\mathsf{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 \mathbf{K} , the number of candidate comparisons per vector is O(\mathbf{K}^{2}) . Each comparison requires computing the distance between two d -dimensional vectors, which costs O(d) . Hence, one NNDescent iteration costs O(|D|\cdot\mathbf{K}^{2}\cdot d) . After T iterations, the total refinement cost is O(T\cdot|D|\cdot\mathbf{K}^{2}\cdot d) . Third, {\mathsf{HRNN}} constructs the reverse-neighbor lists by transposing the ranked {\mathsf{KNN}} graph. Since each of the |D| vectors stores \mathbf{K} ranked neighbors, the ranked {\mathsf{KNN}} graph contains exactly |D|\cdot\mathbf{K} directed neighbor entries. For each entry, {\mathsf{HRNN}} inserts one corresponding reverse posting. Thus, materializing the reverse-neighbor lists costs O(|D|\cdot\mathbf{K}) . Summing the costs of the three phases gives the result. ∎ 4.4. 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 {\mathsf{HRNN}} index after each insertion is prohibitively expensive. Given a newly inserted point o_{\text{new}} , maintenance must synchronize three coupled structures. First, o_{\text{new}} must be incorporated into the {\mathsf{HNSW}} graph to support future proxy retrieval. Second, if o_{\text{new}} becomes one of the top- \mathbf{K} nearest neighbors of existing vectors, the corresponding ranked neighbor lists in G_{{\mathsf{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 o_{\text{new}} into G_{{\mathsf{HNSW}}} and then describe how to minimize the maintenance cost of updating G_{{\mathsf{KNN}}} and \mathbf{R} . Exact Affected Area. The key challenge is identifying the existing points in dataset D affected by the insertion of o_{\text{new}} . Let r_{\mathbf{K}}(o) denote the distance from o to its current \mathbf{K} -th nearest neighbor in G_{{\mathsf{KNN}}} . A vector x is affected if o_{\text{new}} should appear in its top- \mathbf{K} neighbor list after insertion. Formally, the exact affected set is (2) S^{\star}(o_{\text{new}})=\{x\in D\mid\delta(x,o_{\text{new}})\Theta_{u} then break; 10 \hat{S}_{u}(o_{\mathrm{new}})\leftarrow\hat{S}_{u}(o_{\mathrm{new}})\cup\{x\} ; 11 12 // Phase 3: Initialize the new vector L_{\mathrm{new}}\leftarrow top- \mathbf{K} vectors in W(o_{\mathrm{new}}) ranked by \delta(o_{\mathrm{new}},\cdot) ; 13 14 G_{{\mathsf{KNN}}}[o_{\mathrm{new}}]\leftarrow L_{\mathrm{new}} ; 15 16 for each v\in L_{\mathrm{new}} do 17 j\leftarrow rank of v in L_{\mathrm{new}} ; 18 Insert (o_{\mathrm{new}},j) into \mathbf{R}(v) , keeping \mathbf{R}(v) sorted by rank; 19 20 // Phase 4: Refresh affected neighborhoods for each x\in\hat{S}_{u}(o_{\mathrm{new}}) do 21 22 L_{\mathrm{old}}\leftarrow G_{{\mathsf{KNN}}}[x] ; 23 24 r_{\mathbf{K}}(x)\leftarrow\delta(x,G_{{\mathsf{KNN}}}[x,\mathbf{K}]) ; 25 26 if \delta(x,o_{\mathrm{new}})