RaG-Tree: Combining R-Tree and HNSW for Multi-Attribute Range Filtered Approximate Nearest Neighbor Search

RaG-Tree: Combining R-Tree and HNSW for Multi-Attribute Range Filtered Approximate Nearest Neighbor Search Jiawei Liu

Xiang Zhang

Chao Zhang

Renmin University of China jiaweiliu@ruc.edu.cn

Renmin University of China xiangzhang@ruc.edu.cn

Renmin University of China cycchao@ruc.edu.cn

Ju Fan

Xiaoyong Du

Renmin University of China fanj@ruc.edu.cn

Renmin University of China duyong@ruc.edu.cn

arXiv:2608.01255v1 [cs.DB] 2 Aug 2026

ABSTRACT Multi-attribute range-filtered approximate nearest neighbor search (MR-ANNS), which retrieves high-dimensional vectors satisfying multiple attribute constraints, is a fundamental operation in modern AI applications. Existing MR-ANNS indexes either exploit a single attribute for range localization or recursively partition objects along individual attributes, which may limit their ability to exploit attribute correlations for effective range pruning and attribute-vector correlations for efficient nearest-neighbor search. In this paper, we propose RaG-Tree, a unified index that couples an R-tree with partition-aware HNSW graphs for MR-ANNS. RaG-Tree leverages hierarchical R-tree partitions for effective range pruning and adapts the sparsity of each HNSW graph to the local vector distributions within its partition, enabling lightweight indexing and efficient query processing. To support efficient query processing and dynamic updates, we develop a cost-based adaptive search algorithm that minimizes unnecessary graph exploration, together with an efficient index maintenance mechanism for incrementally updating affected partition-aware HNSW graphs. Extensive experiments on three real-world datasets show that RaG-Tree achieves superior query performance over state-of-the-art baselines, while also providing lightweight indexing and fast incremental updates. PVLDB Reference Format: Jiawei Liu, Xiang Zhang, Chao Zhang, Ju Fan, and Xiaoyong Du. RaG-Tree: Combining R-Tree and HNSW for Multi-Attribute Range Filtered Approximate Nearest Neighbor Search. 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/rucjrliu/RaG-Tree_code.

1

INTRODUCTION

Nearest neighbor search (NNS), which retrieves the objects closest to a query vector, has become a fundamental operation in modern AI systems, including recommendation, information retrieval, and 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

retrieval-augmented generation [10, 23–25]. As exact NNS is prohibitively expensive over large-scale and high-dimensional vector data, approximate nearest neighbor search (ANNS) is proposed by trading accuracy for search efficiency, and has been widely adopted by modern vector search systems [19, 35, 39, 46]. In real-world applications, each object is typically associated with not only a high-dimensional vector but also multiple scalar attributes. Queries therefore need to retrieve the top-𝑘 nearest neighbors while satisfying user-specified range predicates over these attributes. We refer to this problem as Multi-attribute Range-filtered Approximate Nearest Neighbor Search (MR-ANNS). For example, an e-commerce query [1, 5] may retrieve products semantically similar to a given image while constraining price, popularity, and inventory to specified ranges. Efficient support for MR-ANNS is thus essential for practical vector retrieval over real-world structured datasets. Limitations of Existing Methods. Most existing range-filtered ANNS indexes are organized around a single filtering attribute [22, 27, 43, 45, 47]. Given a query range, the methods first localize the search to the corresponding attribute interval and then perform ANNS within the resulting search space. However, under multiattribute range queries, only one attribute can be exploited to localize the search, while the remaining attributes are evaluated during or after ANNS. Consequently, the search explores a large number of out-of-range objects that lie outside the multi-attribute query region, significantly affecting query efficiency. Recently, KHI [44] extends range-filtered ANNS to multiattribute queries by recursively partitioning objects along individual attributes using a KD-tree and constructing an HNSW graph [29] for each resulting object partition. Given an MR-ANNS query, it recursively traverses the KD-tree to identify the relevant partitions and performs ANNS on the corresponding HNSW graphs. However, this design has the following two limitations. First, recursively partitioning objects along individual attributes overlooks attribute correlations, leading to inefficient range localization and causing a query to search unnecessarily many HNSW graphs. Second, constructing HNSW graphs without considering various attribute-vector correlations across partitions leads to unnecessary graph exploration over out-of-range objects. Our Proposal. To address these limitations, we propose RaG-Tree, a unified index that tightly couples an R-tree with partition-aware HNSW graphs for efficient MR-ANNS. First, RaG-Tree organizes objects using an R-tree built over all attributes, preserving attribute

2.1

correlations through hierarchical multi-attribute partitions. This enables accurate range localization via Minimum Bounding Rectangle (MBR) pruning, thereby pruning irrelevant object partitions early and significantly reducing the number of HNSW graphs searched for each query. Second, RaG-Tree constructs a partition-aware HNSW graph for each R-tree node, where graph sparsity is adaptively determined according to attribute-vector correlations, reducing unnecessary graph exploration.

Data. This paper considers a set of objects 𝑂 = {𝑜𝑖 | 1 ≤ 𝑖 ≤ 𝑛} associated with 𝑚 attributes {𝐴1, . . . , 𝐴𝑚 }. Specifically, each object 𝑜𝑖 = (x𝑖 , a𝑖 ) consists of a 𝑑-dimensional vector x𝑖 and its attribute values a𝑖 = (𝑎𝑖1, . . . , 𝑎𝑖𝑚 ), where 𝑎𝑖 𝑗 denotes the value of object 𝑜𝑖 on attribute 𝐴 𝑗 . Without loss of generality, we assume all attributes are numeric, since categorical and datetime attributes can be encoded as numeric values.

Challenges and Solutions. Realizing RaG-Tree requires addressing several challenges in query processing and index maintenance. Query Processing. Given an MR-ANNS query, RaG-Tree first identifies the R-tree nodes intersecting with the query predicates and then executes ANNS on the corresponding HNSW graphs. The key challenge is determining the appropriate combination of intersected R-tree nodes across different levels to minimize the overall search cost. To illustrate this trade-off, we consider two baseline strategies. Searching only higher-level nodes executes a few HNSW graphs but incurs excessive search over out-of-range objects. Searching only lower-level nodes improves object filtering but requires executing many HNSW graphs. To address this, we propose a cost-based adaptive search method that adaptively selects the optimal combination of intersected R-tree nodes across different levels, minimizing the overall search cost and substantially reducing query latency. Index Updates. Index updates maintain the R-tree and the partitionaware HNSW graphs under object insertions and deletions. While the R-tree can be updated efficiently through incremental MBR maintenance, efficiently maintaining the HNSW graphs remains challenging. Existing MR-ANNS indexes such as KHI [44] do not support dynamic updates. The key challenge is efficiently propagating each update to multiple HNSW graphs, as an object may belong to multiple R-tree nodes. To address this challenge, we propose a delta HNSW graph mechanism. Insertions are buffered in compact delta HNSW graphs, and deletions are efficiently tracked using bitmaps. Delta HNSW graphs are then adaptively merged into the main HNSW graphs for frequently searched nodes, enabling efficient updates while maintaining high query performance.

Query. An MR-ANNS query is represented as 𝑄 = (q, R, 𝑘), where q is a 𝑑-dimensional query vector, R = (R 1, . . . , R𝑚 ) is a set of query ranges over attributes {𝐴1, . . . , 𝐴𝑚 }, and 𝑘 is the number of nearest neighbors to retrieve. Specifically, each query range R 𝑗 = [𝑙 𝑗 , 𝑢 𝑗 ] specifies the range constraint on attribute 𝐴 𝑗 . The MR-ANNS Problem. The objects satisfying all query range constraints form the candidate object set 𝑂 (R) = {𝑜𝑖 ∈ 𝑂 | 𝑎𝑖 𝑗 ∈ R 𝑗 , ∀ 1 ≤ 𝑗 ≤ 𝑚}. Moreover, we use the Euclidean distance ∥x𝑖 − q∥ to measure the similarity between an object vector x𝑖 and the query vector q. Based on the definitions above, we are ready to define the MRANNS problem as follows. Definition 2.1 (MR-ANNS). Given an object set 𝑂 and a query 𝑄 = (q, R, 𝑘), let 𝑆𝑘 (𝑄) denote the exact top-𝑘 nearest neighbors of q among all objects in 𝑂 (R). The MR-ANNS problem aims to return an approximate top-𝑘 result 𝑆b𝑘 (𝑄). For example, consider the MR-ANNS query 𝑄 = (q, R, 𝑘) illustrated in Figure 1(a), where q is the query vector, R = ([8, 57], [16, 84]), and 𝑘 = 10. The attribute constraints first define a candidate object set consisting of all objects satisfying a1 ∈ [8, 57] and a2 ∈ [16, 84]. Among these candidate objects, the MR-ANNS query returns the approximate top-10 nearest neighbors to q.

2.2

R-Tree

An R-tree is a height-balanced spatial index that recursively partitions objects in the multi-dimensional attribute space [18]. Each node summarizes the objects in its subtree using a Minimum Bounding Rectangle (MBR), enabling efficient pruning of irrelevant partitions during range query processing. Formally, let 𝑇𝑣1 ,𝑉 denote an R-tree rooted at node 𝑣 1 , where 𝑉 is the set of tree nodes. For each node 𝑣 ∈ 𝑉 , let 𝑂 𝑣 ⊆ 𝑂 denote the objects contained in the subtree rooted at 𝑣. The MBR of node 𝑣, denoted by 𝑅𝑣 = (𝑅𝑣,1, . . . , 𝑅𝑣,𝑚 ), bounds the values of all 𝑚 attributes over 𝑂 𝑣 , where

Contributions. Our contributions are summarized as follows. • We propose RaG-Tree, a unified index that couples an R-tree with partition-aware HNSW graphs for MR-ANNS, leveraging R-tree partitions for efficient range pruning and tailoring graph sparsity to attribute-vector correlations across partitions, yielding lightweight indexing and efficient query processing (Section 3). • We propose novel algorithms for query processing (Section 4) and index maintenance (Section 5) tailored to RaG-Tree, enabling low-latency query execution and efficient dynamic updates. • We conduct extensive experiments on well-adopted MR-ANNS benchmarks (Section 6). The results show that, at around 0.95 recall, RaG-Tree improves query throughput by up to 2.8× over baselines, with the advantage growing to more than 10× as the number of attributes increases, while maintaining efficient index construction, lightweight index size and fast updates.

2

Problem Formulation

𝑅𝑣,𝑗 = [𝑙 𝑅𝑗 𝑣 , 𝑢 𝑅𝑗 𝑣 ] with 𝑙 𝑅𝑗 𝑣 = min{𝑎𝑖 𝑗 | 𝑜𝑖 ∈ 𝑂 𝑣 },

𝑢 𝑅𝑗 𝑣 = max{𝑎𝑖 𝑗 | 𝑜𝑖 ∈ 𝑂 𝑣 }.

Consequently, every object 𝑜𝑖 ∈ 𝑂 𝑣 satisfies 𝑎𝑖 𝑗 ∈ 𝑅𝑣,𝑗 for all 1 ≤ 𝑗 ≤ 𝑚. Given a query 𝑄 = (q, R, 𝑘), the R-tree traverses only the nodes whose MBRs intersect the query ranges, i.e., 𝑅𝑣,𝑗 ∩ R 𝑗 ≠ ∅,

PRELIMINARIES

∀ 1 ≤ 𝑗 ≤ 𝑚.

After MBR pruning, let 𝑂 𝑣 (R) denote the subset of objects in 𝑂 𝑣 satisfying the query constraints.

This section first defines the MR-ANNS problem (Section 2.1) and then briefly introduces R-tree and HNSW (Sections 2.2 and 2.3). 2

𝑶𝑶𝒗𝟓 (𝓡) 𝒗𝟓 (𝓡)

𝑄𝑄 = =(𝒒, (𝒒,ℛℛ==(( 8,57 8,57 , , 16,84 16,84 ),),𝑘𝑘==10) 10)

𝑶 𝑶𝟏𝟏

qq

𝑶 𝑶𝟐𝟐

𝑶 𝑶𝟒𝟒

qq

𝑶 𝑶𝟓𝟓

qq

𝑒𝑓 = 10 𝑒𝑓!"#$%& !"#$%& = 10

HNSW HNSW𝓖𝑮𝟒𝟒

HNSW HNSW𝓖𝑮𝟓𝟓

𝑣𝑣(( [8,97] [8,97], ,[15,88] [15,88] 𝑶 𝑶𝟑𝟑

𝑣

𝑣

𝑣&& [8,68] [8,68], ,[15,50] [15,50] 𝑶 𝑶𝟔𝟔

𝑣'' [21,97] [21,97], ,[50,88] [50,88]

𝑂 𝑂--

𝑣𝑣" " [8,38] [8,38], ,[15,45] [15,45]

𝑣𝑣# 𝑣𝑣$ 𝑣𝑣% # $ % [37,68] [37,68], ,[18,50] [18,50] [21,52] [21,52], ,[52,84] [52,84] [58,97] [58,97], ,[50,88] [50,88]

(a) RaG-Tree Structure and Query Processing.

(b) Local HNSW Graphs.

Figure 1: An overview of RaG-Tree, including its R-tree-based index structure and query processing. Each node 𝑣 corresponds to an object subset 𝑂 𝑣 and maintains a local HNSW graph 𝐺 𝑣 constructed over 𝑂 𝑣 .

2.3

HNSW

attribute space. For example, vectors associated with one attribute region may be tightly clustered with small pairwise distances, whereas those associated with another region may be substantially more dispersed. Due to such correlations, the graph sparsity should be adapted to the local vector proximity of each attribute partition, thereby constructing more compact graphs while maintaining efficient ANNS. Therefore, the above two properties motivate a unified index design: attribute correlations are exploited to organize the hierarchical partition structure, while attribute-vector correlations are leveraged to optimize the vector index within each partition.

HNSW is a hierarchical graph-based index for approximate nearest neighbor search (ANNS) [30]. It organizes an object set 𝑂 into a hierarchy of proximity graphs, where each vertex represents an object and each edge connects two neighboring objects according to their vector similarity. The upper layers contain progressively fewer vertices for coarse-grained navigation, while the bottom layer contains all objects for fine-grained nearest-neighbor search. Formally, let 𝐺 denote the HNSW index built over object set 𝑂. The graph sparsity is controlled by the maximum degree parameter 𝑀, which specifies the maximum number of neighbors maintained for each vertex. During index construction, each vertex is assigned a random maximum layer, yielding a hierarchical graph whose expected height is approximately ℎ = ⌊log𝑀 |𝑂 |⌋ + 1. Given a query vector q, HNSW greedily descends from the top layer to the bottom layer and then performs a best-first graph search on the bottom layer. The search is controlled by the parameter 𝑒 𝑓search , which specifies the maximum size of the candidate list maintained during graph exploration, trading off search accuracy and efficiency.

3

Index Structure. As illustrated in Figure 1(a), RaG-Tree is a hierarchical MR-ANNS index that couples an R-tree with partition-aware HNSW graphs. The R-tree recursively partitions the object set according to attribute values, while each tree node serves as a unified indexing unit for both attribute filtering and vector search by maintaining a local HNSW graph over the objects covered by the node. Formally, RaG-Tree constructs a binary R-tree 𝑇𝑣1 ,𝑉 with node set 𝑉 , rooted at node 𝑣 1 ∈ 𝑉 . Each node 𝑣 ∈ 𝑉 is represented by a 5-tuple (𝑂 𝑣 , 𝑅𝑣 , 𝐺 𝑣 , 𝑙𝑐ℎ 𝑣 , 𝑟𝑐ℎ 𝑣 ), where 𝑂 𝑣 denotes the object subset covered by 𝑣, 𝑅𝑣 is the minimum bounding rectangle (MBR) of 𝑂 𝑣 over all 𝑚 attributes, 𝐺 𝑣 is the local HNSW graph built over 𝑂 𝑣 , and 𝑙𝑐ℎ 𝑣 and 𝑟𝑐ℎ 𝑣 denote the left and right child nodes, respectively. In examples involving a specific node 𝑣𝑖 , we simplify the notation by writing (𝑂𝑖 , 𝑅𝑖 , 𝐺𝑖 , 𝑙𝑐ℎ𝑖 , 𝑟𝑐ℎ𝑖 ). Spcifically, for each node 𝑣, RaG-Tree constructs a partitionaware HNSW graph 𝐺 𝑣 over the corresponding object set 𝑂 𝑣 . For ease of presentation, we use node to refer to an R-tree node and vertex to refer to an HNSW vertex. Thus, each each vertex in 𝐺 𝑣 corresponds to an object 𝑜 ∈ 𝑂 𝑣 , while each edge connects neighboring objects according to their Euclidean distances in the vector space. In particular, each local HNSW graph 𝐺 𝑣 is associated with a maximum degree parameter 𝑀𝑣 , which controls its graph sparsity. Since each tree node corresponds to a distinct attribute partition, different local graphs may adopt different values of 𝑀𝑣 to better capture the attribute-vector correlations across partitions. The above hierarchical organization enables RaG-Tree to jointly exploit attribute correlations for effective range pruning and attribute-vector correlations for localized vector indexing.

RAG-TREE

This section first presents the overall design of the proposed RaG-Tree index (Section 3.1), followed by an efficient algorithm for constructing the index (Section 3.2).

3.1

Index Overview

We propose RaG-Tree, a unified index that tightly couples an R-tree with partition-aware HNSW graphs for efficient MR-ANNS. Design Principles. The design of RaG-Tree is motivated by two complementary properties of multi-attribute vector data. First, objects often exhibit strong attribute correlations, where multiple attributes jointly determine the data distribution in the attribute space. For example, products with similar prices are often associated with similar brands or categories, while houses in nearby locations tend to have similar sizes and prices. Due to such correlations, an R-tree can partition attribute space into compact regions with tight MBRs, thereby improving range pruning efficiency. Second, objects exhibit attribute-vector correlations, meaning that the proximity among vectors varies across different regions of the 3

Algorithm 1 RaG-Tree Construction

Example 1. To illustrate the index structure, consider the example in Figure 1(a). The object set 𝑂 is recursively partitioned in the attribute space, e.g., 𝑂 = 𝑂 1 = 𝑂 2 ∪ 𝑂 3 and 𝑂 2 = 𝑂 4 ∪ 𝑂 5 . Each tree node maintains an MBR that bounds the attribute region of its object subset, such as 𝑅2 = ( [8, 68], [15, 50]). As illustrated in Figure 1(b), each R-tree node maintains a local HNSW graph for MR-ANNS. Each local graph is associated with a maximum degree parameter 𝑀𝑣 , which determines its graph sparsity. Since different attribute partitions exhibit different local vector distributions, different graphs may adopt different values of 𝑀𝑣 . For example, the local graphs associated with 𝑂 4 and 𝑂 5 use different maximum degrees (𝑀4 = 2 and 𝑀5 = 4), resulting in different graph sparsities.

Input: Object set 𝑂, Adaptive maximum-degree range [𝑀𝐿 , 𝑀𝐻 ] Output: Constructed RaG-Tree 𝑇𝑣1 ,𝑉 1: function ConstructNode(𝑂 𝑣 ) 2: (𝑣, 𝑅𝑣 , 𝑂𝑙𝑐ℎ 𝑣 , 𝑂𝑟𝑐ℎ 𝑣 ) ← PartitionAndCalcMBR(𝑂 𝑣 ) 3: 𝑀𝑣 ← CalcMaxDeg(𝑂 𝑣 , 𝑅𝑣 , [𝑀𝐿 , 𝑀𝐻 ]) 4: 𝐺 𝑣 ← ConstructHNSWGraph(𝑂 𝑣 , 𝑀𝑣 ) 5: if 𝑂𝑙𝑐ℎ 𝑣 ≠ ∅ ∧ 𝑂𝑟𝑐ℎ 𝑣 ≠ ∅ then 6: 𝑙𝑐ℎ 𝑣 ← ConstructNode(𝑂𝑙𝑐ℎ 𝑣 ) 7: 𝑟𝑐ℎ 𝑣 ← ConstructNode(𝑂𝑟𝑐ℎ 𝑣 ) 8: end if 9: return 𝑣 10: end function 11: 𝑣 1 ← ConstructNode(𝑂) 12: 𝑉 ← {𝑣 1 , . . . , 𝑣 |𝑉 | } by Traverse from Root 𝑣 1 13: return 𝑇𝑣1 ,𝑉

To balance index size, construction cost, and ANNS performance, RaG-Tree adaptively determines the maximum degree 𝑀𝑣 of each local graph through our proposed index construction method presented in Section 3.2. Query Processing. Given a query 𝑄 = (q, R, 𝑘), RaG-Tree first performs MBR pruning on the R-tree to identify all predicateintersecting nodes. It then selects a subset of these nodes whose MBRs collectively cover the query predicates and performs coordinated MR-ANNS over their local HNSW graphs. Specifically, for each selected node 𝑣, RaG-Tree performs MRANNS on the local HNSW graph 𝐺 𝑣 with a local search parameter 𝑒 𝑓𝑣 . The search starts from the entry point at the top layer of 𝐺 𝑣 and greedily traverses each layer toward vertices closer to q, where the closest vertex found at the current layer serves as the entry point for the next lower layer. Upon reaching the bottom layer, RaG-Tree maintains a candidate list of size 𝑒 𝑓𝑣 and iteratively expands the most promising vertices according to their distances to q. Therefore, 𝑒 𝑓𝑣 controls the search breadth of the local graph: a larger value explores more vertices, typically improving recall at the cost of higher search overhead. During the traversal, all visited vertices can be used for graph navigation, whereas only objects satisfying the query predicates R are retained as result candidates. Finally, RaG-Tree merges candidates returned from the selected local HNSW graphs and obtains the approximate top-𝑘 result 𝑆b𝑘 (𝑄).

local graphs and visiting more irrelevant objects. Second, the userprovided search parameter 𝑒 𝑓search should be appropriately allocated among the selected local graphs. To address the challenges, we propose a cost-based adaptive search method that adaptively selects the optimal combination of intersected R-tree nodes across different levels, minimizing the overall search cost and substantially reducing query latency. Please refer to Section 4 for more details.

3.2

HNSW Construction

We recursively construct an RaG-Tree index over the object set 𝑂 from the root node, as outlined in Algorithm 1. For each node 𝑣, RaG-Tree performs the following three steps. • Step 1: Partitioning the object subset 𝑂 𝑣 and computing the corresponding MBR using PartitionAndCalcMBR. • Step 2: Adaptively determining the maximum degree 𝑀𝑣 of the local HNSW graph according to the vector distributions within the attribute partition represented by node 𝑣. • Step 3: Constructing the local HNSW graph 𝐺 𝑣 using ConstructHNSWGraph, and recursively repeating the same procedure for the child nodes.

Example 2. In Figure 1(a), given the query 𝑄 = (q, R = ([8, 57], [16, 84]), 𝑘 = 10), RaG-Tree first performs MBR pruning and identifies the range-intersecting nodes 𝑉 (R) = {𝑣 1, 𝑣 2, 𝑣 3, 𝑣 4, 𝑣 5, 𝑣 6 }, while node 𝑣 7 is pruned. The selected nodes for local graph search should ensure that the union of their MBRs covers the query predicates R, yielding multiple feasible node combinations, such as {𝑣 1 }, {𝑣 2, 𝑣 6 }, and {𝑣 4, 𝑣 5, 𝑣 6 }. Different node combinations exhibit different search behaviors. For example, selecting only 𝑣 1 performs MR-ANNS on a single large local graph, where many visited objects do not satisfy the query ranges. In contrast, selecting all intersecting leaf nodes, i.e., {𝑣 4, 𝑣 5, 𝑣 6 }, reduces unnecessary filtering but requires searching three local graphs. As illustrated in Figure 1(a), RaG-Tree eventually performs coordinated MR-ANNS on the local graphs associated with 𝑣 2 and 𝑣 6 , enabling an effective balance between the number of searched local graphs and the number of visited irrelevant objects.

The main challenge lies in the second step, determining an appropriate maximum degree 𝑀𝑣 for each local HNSW graph 𝐺 𝑣 , as different attribute partitions exhibit different local vector distributions. The key observation is that a local partition with smaller pairwise vector distances requires fewer graph connections, whereas one with larger pairwise distances requires a denser local graph. Therefore, RaG-Tree determines the maximum degree of each local graph according to its local vector distribution. Measuring Local Vector Distributions. To characterize the local vector distribution, RaG-Tree uses the average pairwise vector distance (APD) among the objects in a partition. Specifically, the APD of an object set 𝑂 is defined as

The above example illustrates two key challenges in query processing. First, multiple node combinations may satisfy the query ranges, but exhibit different trade-offs between searching more

APD(𝑂) = 4

1

∑︁

|𝑂 |
2 {𝑜𝑖 ,𝑜 𝑗 } ⊂𝑂

∥x𝑖 − x 𝑗 ∥.

(1)

Our Approach. To balance the trade-off, we propose a cost-based adaptive search algorithm. Specifically, we first develop a cost model for MR-ANNS on a local HNSW graph by considering both graph properties (maximum degree and graph height) and querydependent factors (candidate-list length and range selectivity). We regard the user-provided parameter 𝑒 𝑓search as the global search budget and seek a cost-effective execution plan by selecting an appropriate combination of local graphs and allocating the budget among them, while guaranteeing complete coverage of the query constraints. To this end, we first develop a cost model to estimate the search cost of each candidate local HNSW graph (Section 4.1), and then present a dynamic programming algorithm to jointly optimize local graph selection and search budget allocation (Section 4.2).

For a node 𝑣 associated with the object subset 𝑂 𝑣 , RaG-Tree normalizes its APD by that of the entire object set 𝑂, i.e., 𝛿𝑂 (𝑂 𝑣 ) =

APD(𝑂) − APD(𝑂 𝑣 ) ∈ (−∞, 1]. APD(𝑂)

(2)

A larger value of 𝛿𝑂 (𝑂 𝑣 ) indicates that vectors in 𝑂 𝑣 have smaller pairwise distances than those in the entire set 𝑂, whereas a smaller or negative value indicates larger pairwise distances. Adaptive Maximum Degree Determination. Based on the relative change in APD, RaG-Tree linearly maps the non-negative value of 𝛿𝑂 (𝑂 𝑣 ) to the predefined maximum-degree range [𝑀𝐿 , 𝑀𝐻 ]: 𝑀𝑣 = Round (𝑀𝐻 − max{0, 𝛿𝑂 (𝑂 𝑣 )}(𝑀𝐻 − 𝑀𝐿 )) .

(3)

Based on 𝛿𝑂 (𝑂 𝑣 ), each local partition is assigned an adaptive maximum degree within the predefined range [𝑀𝐿 , 𝑀𝐻 ]. The resulting maximum degree is then used to construct the corresponding local HNSW graph, whose height follows the default HNSW setting:   ℎ 𝑣 = log𝑀𝑣 |𝑂 𝑣 | .

4.1

Note that computing 𝛿𝑂 (𝑂 𝑣 ) requires evaluating the APD of each local partition, which is computationally expensive. Therefore, RaG-Tree estimates APD through object sampling and reuses the sampled statistics of child nodes whenever possible, avoiding redundant computations and reducing the construction overhead.

4

Local MR-ANNS Cost Model

The search cost of MR-ANNS on a local HNSW graph is dominated by high-dimensional vector distance computations, while the costs of other operations, such as range checking and merging local results, can be negligible. Therefore, we measure the search cost by the number of vector distance computations. Cost Formulation. Intuitively, the cost of performing MR-ANNS on a local HNSW graph consists of two components: (1) traversing the upper layers to locate an entry point of the bottom layer, and (2) performing a best-first search on the bottom layer. The former mainly depends on the graph structure, whereas the latter is additionally affected by the local search budget 𝑒 𝑓𝑣 and the selectivity of the query ranges, denoted by sel𝑣 (R). Formally, given a candidate node 𝑣 whose MBR intersects the query ranges, we formulate upper-layer traversal cost and bottom-layer search cost as follows. Upper-layer Traversal Cost. MR-ANNS first greedily descends from the top layer to the bottom layer to locate an entry point. Following the standard HNSW search analysis, each upper layer has an average degree of approximately 𝑀𝑣 /2, and the graph contains ℎ 𝑣 layers  2 in total. Therefore, the traversal cost is estimated by 𝑀2𝑣 ℎ 𝑣 .

COST-BASED ADAPTIVE SEARCH

Given an MR-ANNS query 𝑄 = (q, R, 𝑘), query processing should identify a set of local HNSW graphs whose covered object subsets collectively contain all objects satisfying the range constraints. Different node selections, however, lead to different search behaviors. The key challenge is therefore to determine an appropriate combination of nodes that balances the search cost on individual local graphs and the number of local graphs to search. To better understand this trade-off, we first present two straightforward search strategies as illustrated in Figure 1, and then introduce our cost-based adaptive search algorithm.

Bottom-layer Search Cost. Starting from the entry point, MR-ANNS performs a best-first search on the bottom layer with local search budget 𝑒 𝑓𝑣 . Since only objects satisfying the query ranges can be considered as candidates, approximately 𝑒 𝑓𝑣 /sel𝑣 (R) objects need to be explored to obtain 𝑒 𝑓𝑣 valid candidates. Each explored object visits approximately 𝑀𝑣 neighboring vertices. Therefore, n o the

Single-Node Local Graph Search. Since each internal node covers all objects contained in its descendants, one straightforward strategy is to perform MR-ANNS on only a single local HNSW graph. Specifically, RaG-Tree traverses the R-tree in a top-down fashion and selects the node with the smallest object subset that still covers all objects satisfying the range constraints. It then performs MR-ANNS on the corresponding local HNSW graph. The advantage of this strategy is searching only one local HNSW graph. However, the selected node usually contains many objects outside the query ranges, causing more irrelevant objects to be visited during graph exploration and thus increasing the search cost.

𝑀 𝑒𝑓

bottom-layer search cost is estimated by min |𝑂 𝑣 |, sel𝑣𝑣 ( R𝑣) . Combining the above two components, we estimate the search cost of performing query 𝑄 on node 𝑣 with budget 𝑒 𝑓𝑣 as  2   𝑀 𝑣 𝑒 𝑓𝑣 𝑀𝑣 𝐶b𝑣 (𝑄, 𝑒 𝑓𝑣 ) = . (4) ℎ 𝑣 + min |𝑂 𝑣 |, 2 sel𝑣 (R)

All-Leaf-Nodes Local Graph Search. The other extreme is to perform MR-ANNS on the local HNSW graphs of all leaf nodes whose MBRs intersect the query ranges, and merge the retrieved candidates to produce the final result. This strategy maximizes the pruning capability of the R-tree, since each leaf node contains only a small number of objects outside the query ranges. However, it requires searching many local HNSW graphs, resulting in considerable graph traversal and coordination overhead.

Range Selectivity Estimation. The remaining problem is to estimate the local range selectivity sel𝑣 (R) efficiently. Computing the exact selectivity requires scanning the local object subset 𝑂 𝑣 , which is prohibitively expensive during query processing. Instead of estimating the selectivity directly from the MBR of every node, RaG-Tree assumes local uniformity only at leaf nodes, where each partition is sufficiently compact. The selectivity of internal nodes is then recursively aggregated from their child nodes, 5

Algorithm 2 Cost-based Adaptive Search

yielding more accurate estimates than directly computing overlap ratios on higher-level MBRs. Specifically, we present the estimation methods in leaf and intermediate nodes as follows. Leaf Nodes. For a leaf node 𝑧, we assume objects are uniformly distributed within its MBR 𝑅𝑧 . The range selectivity is therefore estimated by the overlap ratio between the query ranges and the MBR, computed as the product of the overlap ratios on all attributes: c𝑧 (R) = sel

𝑚 Ö |R 𝑗 ∩ 𝑅𝑧,𝑗 | 𝑗=1

|𝑅𝑧,𝑗 |

,

Input: RaG-Tree 𝑇𝑣1 ,𝑉 , query 𝑄 = (q, R, 𝑘), global candidate-list length 𝑒 𝑓search Output: Answer 𝑆b𝑘 (𝑄) 1: function DP(𝑣) 2: 𝑙𝑐𝑜𝑠𝑡 ← 0, 𝑙𝑛𝑜𝑑𝑒𝑠 ← ∅ 3: if ¬𝑙𝑐ℎ 𝑣 is NULL then 4: 𝑙𝑐𝑜𝑠𝑡, 𝑙𝑛𝑜𝑑𝑒𝑠 ← DP(𝑙𝑐ℎ 𝑣 ) 5: end if 6: 𝑟𝑐𝑜𝑠𝑡 ← 0, 𝑟𝑛𝑜𝑑𝑒𝑠 ← ∅ 7: if ¬𝑟𝑐ℎ 𝑣 is NULL then 8: 𝑟𝑐𝑜𝑠𝑡, 𝑟𝑛𝑜𝑑𝑒𝑠 ← DP(𝑟𝑐ℎ 𝑣 ) 9: end if 10: if 𝑙𝑐𝑜𝑠𝑡 + 𝑟𝑐𝑜𝑠𝑡 < 𝐶b𝑣 (𝑄, 𝑒 𝑓𝑣 ) then 11: return 𝑙𝑐𝑜𝑠𝑡 + 𝑟𝑐𝑜𝑠𝑡, 𝑙𝑛𝑜𝑑𝑒𝑠 ∪ 𝑟𝑛𝑜𝑑𝑒𝑠 12: else 13: return 𝐶b𝑣 (𝑄, 𝑒 𝑓𝑣 ), {𝑣 } 14: end if 15: end function 16: 𝑇𝑣1 ,𝑉 ( R ) ← MBRpruning(𝑇𝑣1 ,𝑉 , R) 17: SelEst(𝑣 1 , R) to work out 𝑠 𝑣 (R) for each 𝑣 ∈ 𝑉 (R) 18: EfTuning(𝑣 1 , R, 𝑒 𝑓search ) to set 𝑒 𝑓𝑣 for each 𝑣 ∈ 𝑉 (R) 19: 𝑐𝑜𝑠𝑡, 𝑛𝑜𝑑𝑒𝑠 ← DP(𝑣 1 ) b𝑘 (𝑄) ← top−𝑘 nearest of Ð𝑣 ∈𝑛𝑜𝑑𝑒𝑠 LocalGraphSearch(𝑣, 𝑄, 𝑒 𝑓𝑣 ) 20: 𝑆 b𝑘 (𝑄) 21: return 𝑆

(5)

where |𝐼 | denotes the length of an interval 𝐼 . Internal Nodes. For an internal node 𝑣, the range selectivity is recursively computed as the object-cardinality weighted average of the estimated selectivities of its two child nodes: c 𝑣 (R) = |𝑂𝑙𝑐ℎ 𝑣 | sel c𝑙𝑐ℎ (R) + |𝑂𝑟𝑐ℎ 𝑣 | sel c𝑟𝑐ℎ (R). sel (6) 𝑣 𝑣 |𝑂 𝑣 | |𝑂 𝑣 | Search Budget Allocation. The local MR-ANNS cost model requires the search budget 𝑒 𝑓𝑣 for each candidate node. Starting from the user-provided global search budget 𝑒 𝑓search at the root node, RaG-Tree recursively allocates the budget to the predicateintersecting child nodes in proportion to their estimated numbers of c 𝑣 (R) denote the b𝑣 (R) = |𝑂 𝑣 | sel qualifying objects. Specifically, let 𝑁 estimated number of objects satisfying the query ranges in node 𝑣. Then, for each child node 𝑢 ∈ {𝑙𝑐ℎ 𝑣 , 𝑟𝑐ℎ 𝑣 }, the local search budget is computed by ! b𝑢 (R) 𝑁 𝑒 𝑓𝑢 = Round 𝑒 𝑓𝑣 · . (7) b𝑣 (R) 𝑁

Idea of Dynamic Programming Optimization. A straightforward solution is to enumerate all feasible node combinations and evaluate their total search costs. However, such an approach is computationally prohibitive because the number of feasible combinations grows exponentially with the size of the pruned R-tree. Fortunately, by exploiting the hierarchical structure of the R-tree, the optimization problem exhibits an optimal substructure, enabling an efficient dynamic programming solution. For each candidate node 𝑣, there are only two possible choices.

This allocation strategy assigns a larger search budget to partib𝑣 (R) = tions expected to contain more qualifying objects. Since 𝑁 b b 𝑁𝑙𝑐ℎ 𝑣 (R) + 𝑁𝑟𝑐ℎ 𝑣 (R), the allocated budget is naturally bounded by its parent budget, i.e., 𝑒 𝑓𝑢 ≤ 𝑒 𝑓𝑣 .

4.2

Cost-based Adaptive Search Optimization

• Select 𝑣. Execute MR-ANNS on the local graph of 𝑣 with cost 𝐶b𝑣 (𝑄, 𝑒 𝑓𝑣 ). Since 𝑂 𝑣 covers all objects in its subtree, none of its descendants should be selected. • Optimize the child subtrees. Skip node 𝑣 and recursively optimize the two child subtrees. Since 𝑂𝑙𝑐ℎ 𝑣 ∩ 𝑂𝑟𝑐ℎ 𝑣 = ∅, the two subproblems are independent, and their optimal solutions can be combined directly.

Given the estimated local MR-ANNS cost for each node, we next optimize the problem that determines the node combination that minimizes the overall search cost while guaranteeing coverage of the query ranges. We formulate this optimization problem, and solve the optimization using a dynamic programming algorithm. Optimization Problem. After MBR pruning, each candidate node 𝑣 is associated with an estimated local search cost 𝐶b𝑣 (𝑄, 𝑒 𝑓𝑣 ). The objective is to find a subset of candidate nodes that minimizes the total search cost, i.e., ∑︁ min 𝐶b𝑣 (𝑄, 𝑒 𝑓𝑣 ), 𝑉𝑠 ⊆𝑉 ( R )

Therefore, the optimal search cost rooted at node 𝑣 is computed as n o 𝑂𝑃𝑇 (𝑣) = min 𝐶b𝑣 (𝑄, 𝑒 𝑓𝑣 ), 𝑂𝑃𝑇 (𝑙𝑐ℎ 𝑣 ) + 𝑂𝑃𝑇 (𝑟𝑐ℎ 𝑣 ) , (8)

𝑣 ∈𝑉𝑠

where the first term corresponds to selecting node 𝑣, and the second term corresponds to recursively optimizing its two child subtrees. Therefore, the optimal node combination is obtained by evaluating 𝑂𝑃𝑇 (𝑣 1 ) in a bottom-up traversal of the pruned R-tree.

subject to the constraint that exactly one node is selected on every root-to-leaf path of the pruned R-tree. The above constraint guarantees both coverage of the query ranges and non-overlapping searches. Selecting no node on a rootto-leaf path may miss objects satisfying the query ranges, whereas selecting multiple nodes on the same path results in redundant searches over the same object subset.

DP-based Query Processing Algorithm. Algorithm 2 outlines the query processing procedure. Given an RaG-Tree index 𝑇𝑣1 ,𝑉 , an MR-ANNS query 𝑄 = (q, R, 𝑘), and the user-provided global search budget 𝑒 𝑓search , the algorithm first traverses the index from the root 6

𝑶𝒗𝟓 (𝓡)

graphs, each node maintains an additional sparse delta graph (e.g., Search 𝓖 with 𝒆𝒇 Δ𝐺 inBITMAP Figure 2) to accommodate inserted objects. Conseand 𝚫𝓖 withnewly 𝒆𝒇 3𝒗𝜟 No Keep 𝜟𝓖𝒗 , Add 𝚺𝑪 𝒗 quently,𝚫𝓖updates only affect the lightweight delta graphs, substanAdaptive Delta Merging 5 Query 𝑄 𝑆* 𝑄 $%&'% Σ𝐶,"# > 𝐶," maintenance tially reducing cost. During query processing, 𝓖𝒗 Mergegraph 𝚫𝓖𝒗 into 𝓖𝒗 Yes Search MR-ANNS is executed the original and delta graphs, and Clear 𝚫𝓖𝒗 on both Updated 𝓖 with 𝒆𝒇 their results are merged to produce the final top-𝑘 answer. The remainder of this section presents the index update with delta graphs and the corresponding query processing algorithm.

𝑣'

Deletions 7 Insertions

𝑣% 𝑣!

𝑣& 𝑣"

𝑣#

𝑣$

𝒗

INSERT TO 𝑮𝟕

INSERT TO 𝚫𝑮𝟕

Figure 2: Comparison of Main vs. Delta Graph Insertions.

5.1

and prunes nodes whose MBRs are disjoint from the query ranges, producing the pruned tree 𝑇𝑣1 ,𝑉 ( R ) . For each node in the pruned tree, the algorithm estimates its local range selectivity. As discussed previously, the selectivity of a leaf node is estimated from the overlap between its MBR and the query ranges according to Equation (5), while the selectivity of an internal node is recursively aggregated from its child nodes according to Equation (6). Starting with 𝑒 𝑓𝑣1 = 𝑒 𝑓search , the algorithm further allocates a local search budget 𝑒 𝑓𝑣 to each candidate node based on its estimated number of objects satisfying the query ranges, following Equation (7). With the estimated selectivities and allocated search budgets, the local MR-ANNS cost of each candidate node is computed using Equation (4). The algorithm then evaluates the dynamic programming formulation in Equation (8) in a bottomup manner to determine the node combination with the minimum estimated search cost. Finally, MR-ANNS is executed on the local HNSW graphs of the selected nodes using their respective search budgets 𝑒 𝑓𝑣 . During each local search, only objects satisfying the query ranges are retained as result candidates. The candidates returned from all selected graphs are then merged and ranked by their distances to q, producing the final approximate top-𝑘 result 𝑆b𝑘 (𝑄).

𝒗 𝚫 𝒗

𝒗

Delta-based Incremental Update

Incremental updates in RaG-Tree consist of two components: updating the R-tree for attributes and maintaining the local HNSW graphs for vectors. While attribute updates only modify the MBRs along the insertion path, vector updates are more challenging because incrementally inserting objects into the local HNSW graphs triggers extensive edge modifications. To address this issue, RaG-Tree adopts a delta-based incremental update mechanism, which maintains sparse delta graphs for newly inserted objects while keeping the original graphs unchanged. Besides, object deletions are handled lazily using a bitmap without modifying the index structure. Deleted objects are filtered out during subsequent MR-ANNS according to their bitmap flags. For clarity, we refer to the original local HNSW graph over object set 𝑂 𝑣 as the main graph 𝐺 𝑣 , and the auxiliary graph over newly inserted objects Δ𝑂 𝑣 as the delta graph Δ𝐺 𝑣 . The MBR of each node always bounds the attributes of 𝑂 𝑣 ∪ Δ𝑂 𝑣 . Attribute Update. Given a newly inserted object 𝑜𝑖 = (x𝑖 , a𝑖 ), RaG-Tree first locates its root-to-leaf insertion path according to its attribute values. Along the insertion path, 𝑜𝑖 is inserted into the corresponding delta object set Δ𝑂 𝑣 . If a𝑖 falls outside the current MBR 𝑅𝑣 of a visited node, 𝑅𝑣 is expanded to enclose the new object. Unlike conventional R-trees, RaG-Tree does not perform node splitting or merging after insertions. Since they requires reconstructing all local HNSW graphs in the affected subtree, avoiding structural modifications significantly reduces the update overhead.

Complexity Analysis. The proposed optimization introduces only linear overhead with respect to the size of the pruned R-tree. Specifically, the dynamic programming algorithm evaluates each node exactly once, resulting in a time complexity of O(|𝑉 (R)|). Moreover, the preprocessing steps, including range selectivity estimation and local search budget allocation, each traverse the pruned tree once and therefore also run in O(|𝑉 (R)|) time. In practice, MBR pruning significantly reduces the search space, yielding |𝑉 (R)| ≪ |𝑉 | ≪ |𝑂 |. As a result, the optimization overhead is negligible compared with the subsequent MR-ANNS execution.

5

𝒗

𝒗

Vector Update. Instead of directly inserting new objects into main graph 𝐺 𝑣 , RaG-Tree incrementally maintains a sparse delta graph Δ𝐺 𝑣 for each node. Since newly inserted objects typically constitute only a small fraction of the indexed objects, all insertions are absorbed by the lightweight delta graphs while the main graphs remain unchanged. After locating the insertion path, the new object is inserted into the delta graph of every visited node. To reduce the maintenance cost, the delta graph   is constructed with a smaller

INCREMENTAL INDEX UPDATE

maximum degree: 𝑀𝑣Δ = Round 𝑀𝛼𝑣 . Thus, inserting an object into Δ𝐺 𝑣 requires substantially fewer neighbor searches and edge modifications than inserting it into the main graph, as illustrated in Figure 2.

Maintaining RaG-Tree under object insertions and deletion requires updating both the R-tree for attributes and local HNSW graphs for vectors. While the R-tree can be updated efficiently, incrementally maintaining the local HNSW graphs is more expensive because inserting new objects triggers extensive edge modifications. Specifically, although HNSW supports incremental insertion, a straightforward solution inserts each new object into every affected local graph. As illustrated in Figure 2, inserting only two new objects into 𝐺 7 already causes more edge modifications between the new and existing objects, resulting in high update overhead. To address this, RaG-Tree adopts a delta-based incremental update mechanism. Instead of directly modifying the original local

Update Complexity. Given the local HNSW graph construction parameter 𝑒 𝑓construction = 𝜔𝑐,𝑣 , inserting an object into the main  2 graph 𝐺 𝑣 incurs a cost of approximately 𝑀2𝑣 ℎ 𝑣 +𝑀𝑣 𝜔𝑐,𝑣 , whereas  Δ 2 𝑀 inserting it into the delta graph incurs 2𝑣 ℎ Δ𝑣 + 𝑀𝑣Δ 𝜔𝑐,𝑣 . Since 𝑀𝑣Δ = 𝑀𝑣 /𝛼 and 𝜔𝑐,𝑣 ∝ 𝑀𝑣 in practice, the update cost on the delta graph is approximately 1/𝛼 2 of that on the main graph. 7

6

Therefore, the proposed delta-based incremental update reduces the graph maintenance overhead by roughly a factor of 𝛼 2 .

5.2

EXPERIMENTS

We conduct extensive experiments to evaluate RaG-Tree from three aspects: query performance, incremental update, and index construction. The remainder of this section is organized accordingly. We first evaluate the query performance of RaG-Tree, followed by the evaluation of its incremental update mechanism, and finally its index construction efficiency.

Search over Main and Delta Graphs

After the delta-based incremental update, the attribute index remains unchanged, whereas the vector index is split into two graph structures. Specifically, the MBR 𝑅𝑣 of each node still bounds the attributes of 𝑂 𝑣 ∪ Δ𝑂 𝑣 , allowing the standard MBR pruning procedure to identify all candidate nodes without missing newly inserted objects. The vectors, however, are indexed separately by the main graph 𝐺 𝑣 over 𝑂 𝑣 and the delta graph Δ𝐺 𝑣 over Δ𝑂 𝑣 . Therefore, querying only the main graph would miss newly inserted objects, making it necessary to jointly search both HNSW graphs. For each selected node 𝑣, the main graph is searched using its local candidate-list length 𝑒 𝑓𝑣 . To compensate for the separate navigation on the delta graph, RaG-Tree allocates it an additional candidate-list length proportional to its relative size:   |Δ𝑂 𝑣 | 𝑒 𝑓𝑣Δ = Round 𝑒 𝑓𝑣 . (9) |𝑂 𝑣 |

6.1

Experiment Setup

Datasets. We evaluate all methods on three real-world public datasets: DBLP [2], MSMarco [4], and LAION [3], covering diverse application domains, vector dimensions, and multi-attribute range query characteristics. Their statistics are summarized in Table 1. • DBLP is a scholarly publication dataset with 768-dimensional document embeddings. We use publication metadata, including publication year and statistics of citations, references, and authors, as range query attributes. • MSMarco is a large-scale text retrieval dataset with 384dimensional document embeddings. We use document statistics, including the numbers of words, characters, sentences, unique words, and TF-IDF scores, as range query attributes. • LAION is a large-scale image-text dataset with 512-dimensional image-text embeddings. We use image metadata, including image width, image height, and image-text similarity scores, as range query attributes.

This proportional allocation assigns more search effort to larger delta graphs while introducing only limited overhead when few objects have been inserted. RaG-Tree performs MR-ANNS on the main graph 𝐺 𝑣 with budget 𝑒 𝑓𝑣 and on the delta graph Δ𝐺 𝑣 with budget 𝑒 𝑓𝑣Δ . During both searches, an object is retained as a candidate only if it satisfies all range constraints and is not marked in the deletion bitmap. The candidates returned from the two graphs at all selected nodes are then merged and ranked by their Euclidean distances to q, producing the final approximate top-𝑘 result. Compared with searching only the main graph, jointly searching the delta graph introduces the following additional search cost: ) (  Δ 2 Δ𝑒 𝑓 Δ 𝑀 𝑀 𝑣 𝑣 𝑣 Δ Δ Δ ℎ 𝑣 + min |Δ𝑂 𝑣 |, . (10) 𝐶b𝑣 (𝑄, 𝑒 𝑓𝑣 ) = 2 c 𝑣 (R) sel

For all datasets, we adopt the vector representations and associated metadata constructed in prior work [44]. To support multiattribute numerical range queries, we transform metadata into numerical attributes whenever necessary. Specifically, for metadata that are not directly numerical, we derive numerical statistics from their associated information (e.g., the numbers of citations, references, authors, words, and sentences). This preprocessing yields a unified benchmark with numerical range attributes while preserving the original semantics of the metadata. Queries. To comprehensively evaluate MR-ANNS under different filtering conditions, we generate query workloads covering a broad spectrum of selectivities. This design is also motivated by real-world multidimensional range workloads, whose query selectivities often span several orders of magnitude [28, 38]. For each query, we uniformly sample the number of range constraints 𝑝 from [1, 𝑚] and randomly select 𝑝 attributes without replacement. We then sample a desired query selectivity 𝑠 loguniformly from [10−4, 1], so that query selectivities span multiple orders of magnitude and each order of magnitude is approximately equally represented. Assuming attribute independence only for workload generation, each selected attribute is assigned an expected selectivity of 𝑠 1/𝑝 . Next, we randomly sample an object, use its vector as the query vector, and construct a range constraint around the corresponding value of each selected attribute. The range boundaries are randomly perturbed to ensure query diversity. Queries returning fewer than 𝑘 objects are discarded and regenerated. The exact filtered top-𝑘 results are computed as the ground truth. Unless otherwise specified, we generate 1,000 queries per dataset, set 𝑘 = 10, and use Euclidean distance.

Adaptive Delta Merging. Although the sparse delta graph significantly reduces update overhead, it also introduces additional query cost. Moreover, as insertions accumulate, the delta graph grows larger, making joint search progressively more expensive. To balance update and query efficiency, RaG-Tree adopts an adaptive delta merging strategy based on cost comparison. Specifically, for each node 𝑣, RaG-Tree accumulates the additional search cost incurred on the delta graph over all queries, denoted by Σ𝐶b𝑣Δ , and compares it with the one-time cost of merging the delta graph into the main graph: " # 2 𝑀𝑣 merge b 𝐶𝑣 = |Δ𝑂 𝑣 | ℎ 𝑣 + 𝑀𝑣 𝜔𝑐,𝑣 . (11) 2 A merge is triggered once Σ𝐶b𝑣Δ > 𝐶b𝑣 . After merging, all unmarked objects in Δ𝑂 𝑣 are incrementally inserted into the main graph 𝐺 𝑣 , after which Δ𝐺 𝑣 and Δ𝑂 𝑣 are cleared. Subsequent insertions are accumulated in a new delta graph, forming a repeated cycle of delta-based updates, joint search, and adaptive merging. merge

8

Table 1: Statistics of the datasets. Here, 𝑛, 𝑑, and 𝑚 denote the number of objects, the vector dimensionality, and the number of numerical attributes, respectively. Dataset DBLP MSMarco LAION

𝑛

𝑑

𝑚

Data Type

6,275,270 8,000,000 9,636,707

768 384 512

4 5 3

Text Text Image

Experiment Settings. All experiments were conducted on a server equipped with Intel(R) Xeon(R) Gold 6230 CPUs at 2.10 GHz and 1 TiB of RAM, running Ubuntu 20.04.6 LTS. All methods were implemented in C++ and compiled using GCC 14.3.0. To ensure a fair comparison, all methods were evaluated under the same hardware environment, datasets, query workloads, and execution settings. We ran each experiment three times and reported the average result.

6.2

Search Performance

Figure 3 shows the QPS-Recall curves of all methods. Overall, RaG-Tree achieves the best QPS–Recall trade-off across all three datasets. For example, at Recall around 0.95, RaG-Tree achieves approximately 2.8×, 2.4×, and 1.9× higher QPS than the strongest competing method on DBLP, MSMarco, and LAION, respectively. Next, we analyze these observations in more detail. The comparison with ACORN-𝛾 demonstrates that improving MR-ANNS solely through graph exploration is insufficient. Under the practical 𝛾 = 100 setting, ACORN-𝛾 is less competitive on MSMarco and LAION, where multi-attribute range queries typically exhibit low selectivities, requiring pruning irrelevant objects before graph exploration. Although increasing graph connectivity can improve graph navigation under filtering, it also incurs higher graph construction and traversal costs. DIGRA further shows the limitation of partitioning the attribute space using only a single attribute. It organizes objects according to one selected numerical attribute, while the remaining range constraints are evaluated through post-filtering. As the number of query attributes increases, an increasingly larger fraction of out-of-range objects remain in the searched partitions, leading to unnecessary graph exploration and vector distance computations. These results indicate that effective MR-ANNS requires jointly considering multiple attribute dimensions during range pruning. KHI extends attribute partitioning to multiple dimensions by combining a KD-tree with node-level HNSW graphs. However, it still does not consistently outperform the other baselines on DBLP and MSMarco. This is because the KD-tree partitions the attribute space along one dimension at each split and therefore cannot effectively capture the correlations among multiple attributes. Consequently, multi-attribute range queries may still intersect multiple partially relevant partitions, triggering redundant local graph searches. Moreover, KHI selects local graphs primarily according to range coverage under a predefined node limit, without considering their search costs. These observations suggest that multidimensional partitioning alone is insufficient, and the query execution strategy over local graphs is important. The superior performance of RaG-Tree stems from integrating the above components into a unified design. First, the R-tree organizes objects in the multi-dimensional attribute space, allowing each MBR to jointly capture all attribute dimensions and better preserve the underlying attribute correlations, thereby improving range pruning effectiveness. Second, the correlation-aware local HNSW graphs exploit the attribute-vector correlations across partitions to improve graph exploration efficiency. Finally, cost-based adaptive search adaptively determines the local graph combination and allocates search budgets according to the estimated search costs, avoiding unnecessary graph exploration while maintaining high

Evaluation Metrics. Following prior ANNS work, we use the QPS–Recall curve as the primary evaluation metric, where Recall is computed against the exact filtered top-𝑘 results and QPS measures query throughput. Curves closer to the upper-right corner indicate better search performance. Methods and Settings. We compare RaG-Tree with three representative MR-ANNS methods, DIGRA [22], KHI [44], and ACORN-𝛾 [33], together with two baselines, Pre-filtering and Post-filtering. Pre-filtering first evaluates the range constraints and then performs exact brute-force nearest neighbor search over the qualified objects, whereas Post-filtering first performs ANN search and subsequently filters out objects that do not satisfy the range constraints. All graph-based methods are built upon the NSW/HNSW framework. We use 𝑀 to denote the maximum graph degree and 𝜔𝑐 the graph construction beam width. Unless otherwise specified, all baselines use the parameter settings recommended in their original papers. • RaG-Tree is our proposed method. We set the leaf capacity to 0.1%|𝑂 |, the adaptive degree range to 𝑀𝐿 = 24, 𝑀𝐻 = 32, and the construction beam width of each local graph 𝐺 𝑣 to 𝜔𝑐,𝑣 = 8𝑀𝑣 . • DIGRA organizes objects by a single numerical attribute using a dynamic multi-way tree and maintains node-level NSW graphs. Since DIGRA supports only single-attribute filtering, we index one selected attribute and treat the remaining range constraints as post-filters. We set 𝑀 = 32 and 𝜔𝑐 = 400. • KHI partitions the multi-dimensional attribute space using a KDtree and maintains local HNSW graphs for individual partitions. We set 𝑀 = 32 and 𝜔𝑐 = 128. • ACORN-𝛾 maintains a range-agnostic HNSW graph and performs search over range-induced subgraphs. We set 𝑀 = 32, 𝑀𝛽 = 64, 𝛾 = 100, and 𝜔𝑐 = 𝑀𝛾. The original parameter rule recommends 𝛾 = 1/𝑠 min , which gives 𝛾 = 104 for our minimum query selectivity and leads to prohibitive construction cost. We therefore use 𝛾 = 100, corresponding to a selectivity threshold of approximately 1%, as a practical trade-off between construction cost and query performance. • Pre-filtering and Post-filtering. Pre-filtering builds an R-tree over the numerical attributes and performs exact search over the qualified objects. Post-filtering builds a global HNSW graph and filters the returned objects using the range constraints. We set 𝑀 = 32 and 𝜔𝑐 = 64 for Post-filtering. Note that, for DIGRA and Post-filtering, we additionally increase the intermediate candidate set size up to 10,000 (i.e., 1,000𝑘 for 𝑘 = 10) to fully exploit their search capability and achieve recall comparable to the other methods. 9

ACORN-γ

DIGRA

QPS

103 102 101 100

0.8

0.85

0.9

0.95

KHI

Post-filtering 103

102

102

101

101

100

1

Pre-filtering

103

0.8

0.85

Recall (a) DBLP

0.9

0.95

Recall (b) MSMarco

1

100

0.8

RaG-Tree

0.85

0.9

0.95

1

Recall (c) LAION

Figure 3: Overall QPS vs. recall performance comparison of RaG-Tree and the baselines on three datasets. Table 2: Effect of Cost-based Adaptive Search (CAS). RaG-Tree w/o CAS Dataset

The improvement comes from balancing the trade-off between range pruning and graph exploration. Searching only a single covering node reduces local graph invocations, but its local HNSW graph typically contains many objects outside the query range, resulting in unnecessary graph exploration. Conversely, searching more local graphs improves pruning effectiveness, but also incurs additional graph invocations. CAS explicitly models this trade-off using the proposed cost model, adaptively selecting the node combination with the minimum estimated search cost and allocating the search budget according to the estimated numbers of potentially in-range objects. Consequently, RaG-Tree achieves more effective range pruning while avoiding excessive graph exploration.

RaG-Tree

Recall@10

QPS

Recall@10

QPS

QPS Imp.

DBLP

0.8216 0.9236 0.9891

1,067 462 90

0.8374 0.9315 0.9892

1,285 807 136

20% 75% 51%

MSMarco

0.8255 0.9516 0.9841

658 109 33

0.8302 0.9517 0.9858

802 219 53

22% 101% 61%

LAION

0.8261 0.9443 0.9768

333 44 14

0.8297 0.9454 0.9791

629 167 43

89% 280% 207%

6.4

We evaluate the scalability of RaG-Tree with respect to the number of attributes on LAION by increasing the attribute dimensionality from three to ten and comparing RaG-Tree with KHI and Postfiltering. Each additional attribute is generated by resampling an original attribute to preserve its marginal distribution while remaining approximately independent. We keep the vector embeddings and target selectivities fixed, and recompute the query constraints and exact ground truth for each setting. Figure 4 reports the QPS-Recall curves under different numbers of attributes. All methods gradually degrade as attribute dimensionality increases. Nevertheless, RaG-Tree consistently achieves the best QPS-Recall trade-off. In contrast, Post-filtering mainly suffers a throughput reduction, while KHI has degradation in both throughput and recall. Specifically, at comparable recall levels, RaG-Tree achieves approximately 6.7×–22.0× higher QPS than Post-filtering and 1.9×–11.0× higher QPS than KHI. The different performances reflect the distinct ways in which the methods handle increasingly selective multi-attribute range queries. Post-filtering performs graph exploration without exploiting attribute constraints and therefore cannot reduce the search space as additional attributes are introduced. Consequently, more out-of-range objects are explored, resulting primarily in lower QPS. KHI incorporates multi-attribute partitioning, but its KD-tree performs axis-aligned partitioning along one attribute at each split. As the number of attributes increases, a query tends to intersect more partially relevant partitions, and KHI has to search coarser

recall. Overall, the above designs enable RaG-Tree to consistently achieve the best QPS-Recall trade-off across all three datasets.

6.3

Impact of Attribute Dimensionality

Impact of Cost-based Search Optimization

To evaluate the impact of Cost-based Adaptive Search (CAS), we compare the complete RaG-Tree with RaG-Tree w/o CAS. Both variants use the same index and construction parameters, differing only in the search strategy. RaG-Tree w/o CAS always searches a single R-tree node whose MBR covers the query range and assigns the entire global search budget to its local HNSW graph. In contrast, RaG-Tree employs Cost-based Adaptive Search to select a costeffective combination of R-tree nodes and distribute the global search budget among their local HNSW graphs. Table 2 reports the results. RaG-Tree improves both search efficiency and search quality across all nine evaluated configurations. Specifically, it improves QPS by 20%–280%, with an average speedup of 100.7%. Meanwhile, it also achieves slightly higher Recall in every setting, indicating that the throughput improvement is obtained without sacrificing search accuracy. In particular, the benefit becomes more significant on larger datasets. For example, on LAION, RaG-Tree improves QPS by 1.89×–3.80×, demonstrating that costbased search optimization becomes increasingly important as the search space grows. 10

KHI

Post-filtering

RaG-Tree

500

QPS

200 100 50 20 10

0.76

0.82

0.88

0.94

0.98

0.76

0.82

0.88

0.94

0.98

0.76

0.82

0.88

0.94

0.98

0.76

0.82

0.88

Recall

Recall

Recall

Recall

(a) m = 3

(b) m = 4

(c) m = 5

(d) m = 6

0.94

0.98

0.94

0.98

500

QPS

200 100 50 20 10

0.76

0.82

0.88

0.94

0.98

0.76

0.82

0.88

0.94

0.98

0.76

0.82

0.88

0.94

0.98

0.76

0.82

0.88

Recall

Recall

Recall

Recall

(e) m = 7

(f) m = 8

(g) m = 9

(h) m = 10

25

ImmediateUpdate DeltaUpdate

20 15

250

13.7

10 5

22.5

18.5

9.2 5.7

4.8

4.3 2.0

Average QPS

Index Update Time (103 s)

Figure 4: QPS vs. recall trade-offs of RaG-Tree and representative baselines with varying numbers of attributes on LAION.

256 240

245

234

246

233

239 218

We compare two update strategies. ImmediateUpdate inserts every new object directly into the main HNSW graph at each affected node. DeltaUpdate (𝛼 = 2 by default) instead inserts new objects into the corresponding delta HNSW graphs and incrementally merges them into the main graphs through adaptive delta merging. Both strategies use the same deletion bitmap and differ only in how insertions are handled. Figure 5(a) compares the update efficiency of the two strategies. DeltaUpdate consistently outperforms ImmediateUpdate across all evaluated update ratios, achieving a 3.87×–6.81× speedup with an average of 4.72×. ImmediateUpdate performs graph traversal, neighbor selection, and edge maintenance directly on the main HNSW graph for every inserted object. In contrast, DeltaUpdate first accumulates new objects in lightweight delta graphs and postpones the more expensive maintenance of the main graphs until adaptive delta merging is triggered. By amortizing the graph maintenance cost over multiple insertions, DeltaUpdate substantially reduces the update overhead. The improvement remains significant even under heavy update workloads. For example, at a 50% update ratio, DeltaUpdate still reduces the update time by 74.8%. Figure 5(b) compares the query performance after updates. The average QPS is measured over five recall-aligned operating points, whose maximum Recall difference is only 0.004. DeltaUpdate retains 88.7%–95.4% of the throughput of ImmediateUpdate for update ratios from 20% to 50%, and even slightly outperforms it at the 10% update ratio. The additional query cost comes from searching both the main and delta HNSW graphs before merging their results. As more objects accumulate in the delta graphs, this overhead gradually increases. However, adaptive delta merging effectively bounds the overhead by merging a delta graph once its accumulated search cost exceeds the estimated one-time merging cost.

232 206

200 150 100 50

3.1

0.6

0

10%

20%

30%

40%

50%

0

10%

20%

30%

40%

50%

Data Update Ratio

Data Update Ratio

(a) Update Time

(b) Average QPS

Figure 5: Update time and average QPS of ImmediateUpdate and DeltaUpdate under different update ratios on LAION.

partitions that contain many out-of-range objects or reduce graph exploration, leading to losses in throughput and recall. In contrast, RaG-Tree remains robust because its design scales naturally with increasing attribute dimensionality. The R-tree jointly organizes objects in the multi-dimensional attribute space, allowing each MBR to capture all attribute dimensions and preserve the underlying attribute correlations. This enables effective pruning even for high-dimensional range queries. Moreover, cost-based adaptive search adaptively determines the local graph combination and allocates search budgets according to the estimated search costs, maintaining an effective balance between range pruning and graph exploration.

6.5

Evaluation of Index Updating

We evaluate index updating on LAION with update ratios ranging from 10% to 50%. Each update workload contains equal numbers of insertions and deletions in a randomly shuffled order. Inserted objects are generated by perturbing the vectors of existing objects to avoid duplicates. After each update workload, we recompute the ground-truth results to ensure accurate recall evaluation. 11

Table 3: Index construction time (s) and index size (GB).

indexes target unconstrained ANNS and cannot exploit effectively attribute constraints for MR-ANNS.

Index Construction Time (s) Dataset

ACORN-𝛾

DIGRA

KHI

RaG-Tree

DBLP MSMarco LAION

3,246,360 2,308,722 2,569,788

248,580 319,375 298,624

61,247 103,803 96,532

59,244 66,110 84,976

Attribute-Filtered Approximate Nearest Neighbor Search. Existing methods for attribute-filtered ANNS integrate attribute constraints into either query processing or index construction, and can generally be divided into filtering-based approaches and specialized indexes. Filtering-based approaches combine ANN indexes with pre- or post-filtering and are widely adopted in vector databases such as Pgvector [35], Milvus [39], and Qdrant [36]. They support flexible filters but handle attribute filtering and graph search independently. Specialized indexes incorporate attribute information into the index structure and can be divided into predicateagnostic and predicate-specific approaches. Predicate-agnostic indexes, such as ACORN [33], Navix [37], and Rwalks [6], support diverse filters by augmenting proximity graphs or adapting graph traversal. Predicate-specific indexes target particular filter types: equality-filtered ANNS indexes [17, 40] focus on categorical attributes, while range-filtered ANNS indexes focus on numerical range constraints. Most existing range-filtered methods, including SeRF [47], WST [12], iRangeGraph [43], WoW [41], and DIGRA [22], support only single-attribute range filtering. KHI [44] extends this line of work to MR-ANNS by recursively partitioning with nodelocal HNSW graphs, still inefficient. In contrast, RaG-Tree jointly organizes multiple numerical attributes using an R-tree, exploits attribute and attribute-vector correlations, and optimizes graph exploration via cost-based adaptive search for more effective range pruning and graph exploration in MR-ANNS.

Index Size (GB) Dataset DBLP MSMarco LAION

6.6

ACORN-𝛾

DIGRA

KHI

RaG-Tree

23.1 18.0 26.2

25.0 23.8 30.0

9.0 26.1 21.3

9.2 12.4 15.6

Evaluation on Index Construction

Table 3 reports the index construction time and index size of all specialized filtered ANN indexes. Pre-filtering and Post-filtering are excluded because they do not construct MR-ANNS indexes. RaG-Tree achieves the shortest index construction time on all three datasets. Compared with the fastest competitor (KHI), it reduces construction time by 3.3%, 36.3%, and 12.0% on DBLP, MSMarco, and LAION, respectively, corresponding to an average speedup of 1.25×. Although RaG-Tree builds a local HNSW graph at every R-tree node, its partition-aware graph construction assigns smaller maximum degrees to partitions whose local vectors are easier to navigate, thereby reducing the costs of neighbor selection and edge maintenance. Moreover, the required attribute-vector correlations are estimated from sampled objects rather than exhaustive pairwise vector distances, introducing little additional overhead. RaG-Tree also achieves the smallest index size on MSMarco and LAION. On DBLP, its 9.2 GB index is within 2.2% of KHI, which achieves the smallest index size. The lightweight index mainly comes from the R-tree, which jointly partitions the multidimensional attribute space and therefore requires fewer local HNSW graphs than alternative partition structures. In addition, partition-aware graph construction avoids assigning unnecessarily large maximum degrees to all local graphs, further reducing the number of stored graph edges.

7

8

CONCLUSION AND FUTURE WORK

In this paper, we have introduced RaG-Tree, a unified index for multi-attribute range approximate nearest neighbor search (MRANNS). RaG-Tree tightly couples an R-tree with partition-aware HNSW graphs, enabling efficient multi-dimensional range pruning and graph exploration within a unified framework. Specifically, the R-tree preserves attribute correlations through hierarchical multi-attribute partitions, while partition-aware HNSW graphs exploit local attribute-vector correlations to adapt graph sparsity to different partitions. Building upon this index structure, we have proposed cost-based adaptive search to optimize local graph selection and search budget allocation, together with a delta-based incremental update mechanism for efficient index maintenance under dynamic workloads. Extensive experiments on three real-world datasets have demonstrated that RaG-Tree consistently achieves the best QPS-Recall trade-off, while also providing efficient index construction, lightweight storage, and fast incremental updates. Several directions remain for future work. First, while this paper focuses on numerical attributes with range constraints, extending RaG-Tree to support heterogeneous filter types, such as categorical, textual, and spatial filters, is an important direction. Second, further integrating adaptive workload modeling into both index organization and query processing may enable RaG-Tree to optimize itself under evolving data distributions and query workloads.

RELATED WORK

Approximate Nearest Neighbor Search Approximate nearest neighbor search (ANNS) methods [26, 32] can be broadly classified into hashing-based [7, 8, 11, 42], partition-based [9, 15, 16, 21, 31], and graph-based [13, 14, 20, 29, 30, 34] approaches. Hashing-based methods provide theoretical approximation guarantees but typically require substantial space to achieve high accuracy. Partitionbased methods improve search efficiency by restricting queries to a small number of vector partitions, often combined with vector quantization for compact storage. Graph-based methods, such as HNSW [30], NSG [14] and DiskANN [20], organize vectors as proximity graphs and perform greedy graph exploration, achieving an effective trade-off between search accuracy and efficiency. These 12

REFERENCES

tasks. Advances in neural information processing systems 33 (2020), 9459–9474. [26] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2019), 1475–1488. [27] Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search. Proceedings of the VLDB Endowment 18, 4 (2024), 1118–1130. [28] Qiyu Liu, Maocheng Li, Yuxiang Zeng, Yanyan Shen, and Lei Chen. 2025. How good are multi-dimensional learned indexes? An experimental survey. The VLDB Journal 34, 2 (2025), 17. [29] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68. [30] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836. [31] Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence 36, 11 (2014), 2227–2240. [32] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems. The VLDB Journal 33, 5 (2024), 1591–1615. [33] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. Acorn: Performant and predicate-agnostic search over vector embeddings and structured data. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27. [34] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient approximate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Management of Data 1, 1 (2023), 1–27. [35] Pgvector. 2025. Pgvector: Open-source vector similarity search for Postgres. https://github.com/pgvector/pgvector. 2025/10/12. [36] Qdrant. 2025. Qdrant: High-Performance Vector Search at Scale. https://qdrant. tech/. 2025/10/12. [37] Gaurav Sehgal and Semih Salihoğlu. 2025. NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance. Proceedings of the VLDB Endowment 18, 11 (2025), 4438–4450. [38] Stefan Sprenger, Patrick Schäfer, and Ulf Leser. 2018. Multidimensional range queries on modern hardware. In Proceedings of the 30th International Conference on Scientific and Statistical Database Management. 1–12. [39] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 international conference on management of data. 2614–2627. [40] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2023. An efficient and robust framework for approximate nearest neighbor search with attribute constraint. Advances in Neural Information Processing Systems 36 (2023), 15738–15751. [41] Ziqi Wang, Jingzhe Zhang, and Wei Hu. 2025. WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–27. [42] Jiuqi Wei, Botao Peng, Xiaodong Lee, and Themis Palpanas. 2024. DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search. Proceedings of the VLDB Endowment 17, 9 (2024), 2241–2254. [43] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S Jensen. 2024. irangegraph: Improvising range-dedicated graphs for range-filtering nearest neighbor search. Proceedings of the ACM on Management of Data 2, 6 (2024), 1–26. [44] Yuanhang Yu, Dawei Cheng, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2026. Efficient Approximate Nearest Neighbor Search under Multi-Attribute Range Filter. arXiv preprint arXiv:2602.15488 (2026). [45] Fangyuan Zhang, Mengxu Jiang, Guanhao Hou, Jieming Shi, Hua Fan, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. [46] Xiang Zhang, Chao Zhang, Ju Fan, Guoliang Li, and Xiaoyong Du. 2026. VecBench: A Controllable Benchmark for Filtered Vector Search:[Experiments & Analysis]. Proceedings of the ACM on Management of Data 4, 3 (SIGMOD (2026), 1–27. [47] Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. Serf: Segment graph for range-filtering approximate nearest neighbor search. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–26.

[1] [n.d.]. Amazon. https://www.amazon.com DBLP. https://open.aminer.cn/open/article?id= [2] [n.d.]. 655db2202ab17a072284bc0c [3] [n.d.]. LAION. https://laion.ai/blog/laion-400-open-dataset [4] [n.d.]. MSMarco. https://microsoft.github.io/msmarco [5] [n.d.]. Taobao. https://www.taobao.com [6] Anas Ait Aomar, Karima Echihabi, Marco Arnaboldi, Ioannis Alagiannis, Damien Hilloulin, and Manal Cherkaoui. 2025. RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. [7] Alexandr Andoni and Piotr Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51, 1 (2008), 117–122. [8] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. Advances in neural information processing systems 28 (2015). [9] Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2015. Cache locality is not enough: high-performance nearest neighbor search with product quantization fast scan. Proceedings of the VLDB Endowment 9, 4 (2015), 288–299. [10] Rihan Chen, Bin Liu, Han Zhu, Yaoxuan Wang, Qi Li, Buting Ma, Qingbo Hua, Jun Jiang, Yunlong Xu, Hongbo Deng, et al. 2022. Approximate nearest neighbor search under neural similarity metric for large-scale recommendation. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 3013–3022. [11] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Localitysensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry. 253–262. [12] Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate nearest neighbor search with window filters. In Proceedings of the 41st International Conference on Machine Learning. 12469–12490. [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. [14] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment 12, 5 (2019), 461–474. [15] Jianyang Gao and Cheng Long. 2024. Rabitq: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27. [16] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization. IEEE transactions on pattern analysis and machine intelligence 36, 4 (2013), 744–755. [17] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, et al. 2023. Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. In Proceedings of the ACM Web Conference 2023. 3406–3416. [18] Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD international conference on Management of data. 47–57. [19] Yizheng Huang and Jimmy Xiangji Huang. 2026. A survey on retrievalaugmented text generation for large language models. Comput. Surveys 58, 12 (2026), 1–38. [20] 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. Advances in neural information processing Systems 32 (2019). [21] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128. [22] Mengxu Jiang, Zhi Yang, Fangyuan Zhang, Guanhao Hou, Jieming Shi, Wenchao Zhou, Feifei Li, and Sibo Wang. 2025. DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. [23] Wenqi Jiang, Shuai Zhang, Boran Han, Jie Wang, Bernie Wang, and Tim Kraska. 2025. Piperag: Fast retrieval-augmented generation via adaptive pipeline parallelism. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1. 589–600. [24] Omar Khattab and Matei Zaharia. 2020. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval. 39–48. [25] 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 13

Related documents

• Approximate Nearest Neighbor Search with Graph Range Filters#329177
• Unified Dominance Graph for Interval-Predicate Approximate Nearest Neighbor Search#303305
• Minimum Description Length based Granular-Ball Tree Regularization for Spectral Clustering#1131542
• When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting#222617
• Edu-QuRating: Multi-Dimensional Educational Data Curation with Distilled Pairwise Judgements#999319