arXiv CSopen access

A GPU-Accelerated Framework for Multi-Attribute Range Filtered Approximate Nearest Neighbor Search

arXiv:2604.20121v1 [cs.DB] 22 Apr 2026

A GPU-Accelerated Framework for Multi-Attribute Range Filtered Approximate Nearest Neighbor Search Zhonggen Li

Haoran Yu

Zhejiang University [email protected]

Zhejiang University [email protected]

Yifan Zhu

Yunjun Gao

Zhejiang University [email protected]

Zhejiang University [email protected]

Abstract Range-filtered approximate nearest neighbor search (RFANNS) is increasingly critical for modern vector databases. However, 22.4× existing solutions suffer from severe index inflation and construction 8.5× overhead. Furthermore, they rely exclusively on CPUs for the heavy indexing and query processing, failing to leverage the powerful computational capabilities of GPUs. In this paper, we present Garfield, a GPU-accelerated framework for multi-attribute range filtered ANNS that overcomes these bottlenecks through designing a lightweight index structure and hardwareaware execution pipeline. Garfield introduces the GMG index, which partitions data into cells and builds local graph indexes. By adding a constant number of cross-cell edges, it guarantees linear storage and indexing overhead. For queries, Garfield utilizes a cluster-guided ordering strategy that reorders query-relevant cells, enabling a highly efficient cell-by-cell traversal on the GPU that aggressively reuses candidates as entry points across cells. To handle datasets exceeding GPU memory, Garfield features a cell-oriented out-of-core pipeline. It dynamically schedules cells to minimize the number of active queries per batch and overlaps GPU computation with CPU-to-GPU index streaming. Extensive evaluations demonstrate that Garfield reduces index size by 4.4×, while delivering 119.8× higher throughput than state-of-the-art RFANNS methods. PVLDB Reference Format: Zhonggen Li, Haoran Yu, Yifan Zhu, and Yunjun Gao. A GPU-Accelerated Framework for Multi-Attribute Range Filtered Approximate Nearest Neighbor Search. PVLDB, 20(2): XXX-XXX, 2027. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/ZJU-DAILY/Garfield.

1

Introduction

The rapid growth of unstructured data has made Approximate Nearest Neighbor Search (ANNS) a core component of modern database systems, enabling applications like information retrieval [5, 27, 49], recommendation [18, 35, 53], and retrieval-augmentation generation (RAG) [19, 26, 64]. In real-world scenarios, unstructured objects This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 20, No. 2 ISSN 2150-8097. doi:XX.XX/XXX.XX

22.4×

15.6× 6.3×

8.5×

(a) Comparison of index size.

(b) Comparison of index construction.

Figure 1: Vanilla ANNS index (HNSW[33]) vs. RFANN indexes (iRangeGraph[52] and UNIFY[29]) on SIFT1M. (e.g., videos, documents) are often coupled with structured numeric attributes (e.g., timestamp, duration). Consequently, modern systems increasingly demand range-filtered ANNS (RFANNS) [44, 48], which answer vector similarity queries while enforcing structured attribute range predicates to retrieve more relevant results [25]. For instance, video platforms such as YouTube enable users to retrieve videos within a specific duration and release date range [52, 66]. However, efficiently supporting multi-attribute RFANNS poses significant algorithmic and system bottlenecks. Existing state-ofthe-art RFANNS solutions [17, 29, 40, 47, 52, 66] typically partition the dataset based on attribute values and employ graph-based indexes to achieve efficient retrieval. To guarantee index connectivity under strict filtering constraints, they extensively augment the base graphs with numerous auxiliary edges across different attribute partitions. As shown in Figure 1, this paradigm incurs up to 15.6× increase in index size and 22.4× construction overhead compared to vanilla ANNS [33]. Crucially, these specialized structures are primarily optimized for single-attribute filtering [56]. Extending them to multi-attribute scenarios presents a fundamental dilemma: constructing dedicated indexes for each attribute leads to prohibitive storage costs [55], whereas relying on a single-attribute index with post-filtering for the remaining attributes severely degrades search efficiency and accuracy [52]. Furthermore, these bottlenecks are further amplified by hardware constraints. Existing RFANNS frameworks are primarily CPUbased, where construction and traversal of the massive index structure impose additional pressure on the limited computing power of CPUs, severely bounding the overall system throughput [29, 52]. While GPUs have achieved significant success in accelerating vanilla ANNS by leveraging massive hardware parallelism [28, 36, 57, 62], transplanting this success to RFANNS is non-trivial. The heavily inflated RFANNS indexes rapidly exhaust the limited GPU High-Bandwidth Memory (HBM). Worse still, the query-dependent, dynamic subgraph assembly commonly used in RFANNS destroys

6

indexes [16, 21, 43], Garfield’s unique multi-graph traversal mechanism renders them incompatible. More critically, the highly variable nature of multi-attribute query ranges means the number of cells required per query varies dramatically. Naively dispatching cells to the GPU leads to severe workload imbalance and heavy contention for memory bandwidth and registers, ultimately degrading throughput. To overcome this challenge, we develop a cell-oriented out-of-core pipeline that streams the GMG index to the GPU in batches of cells. Each batch is constructed under explicit HBM constraints to ensure memory usage remains bounded and stable. More importantly, Garfield formulates batch scheduling as an optimization problem aimed at minimizing the number of active queries per batch, which is a key factor we identified for reducing concurrent memory pressure and improving GPU throughput. Using a lightweight greedy strategy, Garfield allocates cells to batches to balance both the batch size and the effective parallel workload. At runtime, Garfield pipelines CPU-to-GPU data transfers with GPU computation across batches, effectively hiding I/O latency behind computation and enabling scalable multi-attribute RFANNS on datasets that exceed GPU memory limits. In summary, this paper makes the following contributions.

memory coalescing and leads to severe warp divergence, rendering conventional GPU-based ANNS optimizations entirely ineffective for range-filtered workloads. To overcome the above bottlenecks, we propose Garfield, a GPUaccelerated framework for multi-attribute range filtered approximate nearest neighbor search. Garfield tightly couples a specialized lightweight index structure with a hardware-aware execution pipeline. However, designing such an end-to-end framework on GPUs entails addressing three primary challenges. Challenge I: How to design a multi-attribute RFANNS index with minimal construction and storage overhead? Existing RFANNS indexes introduce massive amounts of redundant edges to maintain graph connectivity under filtering constraints [17, 52, 66]. This leads to nearly 16× index inflation and substantial construction overhead, strictly limiting their viability on memory-constrained GPUs. Furthermore, extending these single-attribute designs to multi-attribute scenarios makes the problem more serious, as it either requires maintaining dedicated indexes for every attribute combination or relies on inefficient post-filtering [52, 55]. To address this, Garfield proposes a highly efficient, grid-based multi-graph (GMG) index. Instead of constructing per-attribute indexes, Garfield partitions the vector data into a fixed number of disjoint grid cells using a cardinality-balanced quantile strategy, subsequently building a GPU-friendly graph within each grid cell. To enable cross-cell navigation, each node maintains only a small constant number of approximate nearest neighbors (e.g., 2) for other cells, which are efficiently established after the intra-cell graphs are built. These inter-cell edges introduce a predictable, linear storage overhead, eliminating the massive redundancy and construction costs of prior RFANNS indexes while fitting into GPU memory. Challenge II: How to achieve high-throughput queries on the GMG index with a GPU-friendly paradigm? During query processing, state-of-the-art methods typically identify target subgraphs and dynamically assemble them into a larger graph before searching [29, 52]. Applying such a dynamic assembly to the GMG index would degrade search accuracy due to the limited inter-cell edges. Furthermore, it would incur high edge-assembly overhead that disrupts GPU memory coalescing. Conversely, independently searching these subgraphs in serial is also inefficient. Garfield addresses this by introducing a novel multi-graph traversal strategy that iteratively searches the relevant subgraphs rather than merging them. For a given query, Garfield first identifies the cells intersecting the range predicates, and then processes them in an optimized sequence. After retrieving results from one cell, Garfield leverages the current nearest neighbors to expand via inter-cell edges, yielding high-quality entry points for subsequent cells. Additionally, it applies a robust entry-selection mechanism to mitigate inaccurate cross-cell hops. Within this paradigm, the traversal order of the cells impacts the quality of the propagated entry points. Thus, Garfield incorporates a cluster-guided cell ordering strategy. By estimating the cardinality of each cell, it prioritizes the most promising cells to enable a highly efficient cell-by-cell traversal. Challenge III: How to support efficient RFANNS on large-scale datasets that exceed GPU memory capacity? GPUs offer high parallelism but are constrained by limited HBM, making it infeasible to keep large RFANNS indexes entirely in memory. While various out-of-core ANNS techniques are proposed for standard graph

• Lightweight multi-graph index. We propose GMG, an index that builds subgraphs per cell and adds inter-cell edges to enable multi-attribute RFANNS with linear, predictable memory and build overhead on GPUs (Section 3). • Hardware-aware query framework. We introduce a novel query framework that reorders and iteratively searches relevant cells, reusing candidates as robust entry points to achieve high-throughput RFANNS on GPUs (Section 4). • Cell-oriented out-of-core pipeline. We develop an out-of-core execution pipeline that batches and streams cells under HBM constraints, optimizes batch composition, and overlaps data transfers with GPU computation (Section 5). • Extensive experiments. We conduct comprehensive experiments on 6 datasets, demonstrating that Garfield outperforms existing RFANNS methods by 119.8× (Section 6). The paper is organized as follows. Section 2 presents the background. Section 3 introduces the index structure. Section 4 describes the query processing framework. Section 5 introduces the out-ofcore RFANNS pipeline. Section 6 reports the experimental results. Section 7 concludes the paper.

2

Preliminaries

In this section, we formalize the problem setting and introduce existing methods for range-filtered nearest neighbor search.

2.1

Problem Definition

In practical applications, unstructured objects are typically represented as high-dimensional vectors [15, 37, 46] and are frequently coupled with structured numeric attributes [20, 65]. To yield more relevant search results, these numeric attributes are commonly leveraged to constrain the vector retrieval process. For instance, a user might search for restaurants matching a specific textual description while filtering for desired price and distance ranges. By embedding these descriptions into vectors, this paradigm can be 2

𝑆 disjoint segments, whereas DIGRA [17] employs a multi-way tree to partition the dataset according to the attribute. UNIFY and DIGRA yield space complexities of 𝑂 (𝑛𝑀𝑆) and 𝑂 (𝑛𝑀 log 𝑛), respectively. WoW [47] employs a weighted balanced tree and designs hierarchical window graphs to support incremental indexing, incurring a space complexity of 𝑂 (𝑐𝑛 + 𝑛𝑀 ⌈log𝑜 𝑛/2 + 1⌉), where 𝑐 is the storage overhead of each tree node and 𝑜 is typically set to 4. Compared to vanilla ANNS graph indexes, which require a general space complexity of 𝑂 (𝑛𝑀), existing state-of-the-art RFANNS indexes typically inflate the index size by a factor of log 𝑛 or 𝑆, resulting in severe storage bottlenecks. Besides dedicated indexes for RFANNS, recent studies have proposed various methods for attribute-filtered ANNS, including label-filtered [4, 7, 11, 45, 50] and predicate-agnostic [8, 31, 38, 42, 54, 61] ANNS. Although some of them can be employed for RFANNS, they face efficiency issues for RFANNS compared to dedicated indexes.

formalized as vector retrieval subjected to multi-attribute range constraints, commonly referred to as range-filtered nearest neighbor search (RFNNS) [25, 29]. Formally, let D be a dataset comprising 𝑛 objects. Each object 𝑜 ∈ D is represented as a tuple 𝑜 = (𝑣, 𝐴), where 𝑣 ∈ R𝑑 is a 𝑑-dimensional vector and 𝐴 = {𝑎 1, 𝑎 2, ..., 𝑎𝑚 } is a set of 𝑚 numeric attributes. The exact RFNNS problem is defined as follows. Definition 1. Given a dataset D with 𝑛 objects {𝑜 1, ..., 𝑜𝑛 }, a distance metric 𝑑𝑖𝑠 (·, ·), and a query 𝑄 = (𝑞, 𝐹 ), where 𝑞 ∈ R𝑑 is the query vector and 𝐹 = {[𝑙𝑖 , 𝑟𝑖 ]|𝑖 ∈ 𝑀 } denotes the range predicates over a subset of attributes 𝑀 ⊆ {1, ..., 𝑚}. The object of RFNNS is to identify a 𝑘-element subset 𝑅𝑄 ⊆ D such that: (1) every object 𝑜 = (𝑣, {𝑎 1, ..., 𝑎𝑚 }) ∈ 𝑅𝑄 satisfies 𝑙𝑖 ≤ 𝑎𝑖 ≤ 𝑟𝑖 for all 𝑖 ∈ 𝑀; and (2) for any object 𝑢 ∈ D\𝑅𝑄 , 𝑑𝑖𝑠 (𝑣, 𝑞) ≤ 𝑑𝑖𝑠 (𝑢, 𝑞). Due to the prohibitive computational overhead of exact RFNNS, recent research primarily focuses on its approximate variant, i.e., range-filtered approximate nearest neighbor search (RFANNS). These approaches design specialized index structures to accelerate search efficiency while maintaining high recall. In line with these methods, our work also investigates the solutions for efficient RFANNS.

2.2

2.2.2 Solutions for Multi-Attribute RFANNS. The aforementioned methods are primarily designed for single-attribute RFANNS. To extend them to multi-attribute RFANNS, two strategies are commonly adopted [52, 55]. The first strategy involves constructing an independent index for each attribute and employing post-filtering for conjunctions. This incurs significant indexing and storage overheads, given the already substantial footprint of a single-attribute index. The second strategy constructs an index on a single primary attribute and filters other attributes during the search process. For example, iRangeGraph traverses the index via a greedy strategy, visiting out-of-range neighbors with a probability of 𝑝 (0 ≤ 𝑝 ≤ 1) to maintain graph connectivity. Although this approach maintains a manageable index size, its search efficiency is limited by the runtime filtering of neighbors. Recently, KHI [56] introduced a dedicated index for multi-attribute RFANNS. Similar to single-attribute counterparts, it partitions the dataset across multiple attributes using a KD-tree. Within each KD-tree node, it constructs a single-level HNSW index, yielding a space complexity of 𝑂 (𝑛𝑀 log 𝑛𝑐 ), where 𝑐 denotes the capacity of leaf nodes. During query processing, it dynamically reconstructs the neighbors in the index based on the query range and traverses on the reconstructed graph. While KHI achieves better efficiency than naive extensions of single-attribute indexes, it still suffers from severe index inflation. Furthermore, directly transplanting this index structure to GPUs fails to exploit their massive parallelism. The traversal of the KD-tree and dynamic neighbor reconstruction induce severe warp divergence and irregular memory accesses, limiting the computational throughput.

Related Work

To efficiently perform general ANNS, various types of indexes have been proposed, including tree-based [32, 58], hash-based [60, 63], quantization-based [30, 59], and graph-based [10, 34, 39] methods. Among these, graph-based methods consistently demonstrate superior performance in terms of both accuracy and efficiency [5, 13, 41]. These methods model each vector as a node in the graph, connecting it to its nearest neighbors. Query processing typically relies on greedy graph traversal to locate the approximate nearest neighbor vectors for a given query. Given their remarkable performance, existing state-of-the-art RFANNS solutions also adopt graph-based indexes as their foundational structure [17, 29, 40, 52, 66]. 2.2.1 Solutions for Single-Attribute RFANNS. Directly applying vanilla graph-based indexes to RFANNS is ineffective. Attribute filters often prune pivot nodes in the search path, thereby disrupting graph connectivity and hindering greedy traversal. Consequently, existing RFANNS methods introduce various augmentation strategies to maintain the graph connectivity under filtering constraints. For instance, SeRF [66] proposes constructing dedicated graph indexes for all possible query ranges, which incurs prohibitive construction overhead. To mitigate the indexing overhead, iRangeGraph [52] organizes objects using a segment tree based on their numeric attribute. Specifically, the full attribute range is partitioned into 2𝑖 disjoint segments at the 𝑖-th level of the segment tree. By building a Relative Neighborhood Graph (RNG) index within each tree node, iRangeGraph incurs a space complexity of 𝑂 (𝑛𝑀 log 𝑛), where 𝑛 is the dataset size and 𝑀 is the maximum graph degree. During query processing, iRangeGraph dynamically constructs a composite subgraph by retrieving edges from the pre-built indexes located in the tree nodes that intersect the target range. Subsequently, it performs a greedy search on this assembled subgraph to achieve RFANNS. Other state-of-the-art methods adopt a similar paradigm: partitioning the dataset into several segments based on the attributes and constructing independent indexes within each segment. For example, UNIFY [29] evenly divides the dataset into

2.2.3 RFANNS on GPUs. While GPUs have demonstrated superior performance in accelerating vanilla ANNS [16, 23, 62] and label-filtered ANNS [51], leveraging them for RFANNS remains largely unexplored. Currently, there are two straightforward strategies for executing RFANNS on GPUs. (1) Pre-filtering strategy first scans the dataset to identify candidates satisfying the range predicates, followed by a brute-force linear scan on the filtered subset. This strategy completely abandons the high-performance graph index because pre-filtering fundamentally disrupts its connectivity, resulting in severe inefficiencies under low query range selectivity. (2) Post-filtering strategy performs vanilla ANNS and applies the range filters to the retrieved results. Under high query range selectivity, this strategy executes substantial redundant distance 3

Algorithm 1: Construction of the GMG index Input: dataset D = {𝑜 1, ..., 𝑜𝑛 }, partitioned attributes count 𝑝, number of cells 𝑆, number of segments 𝑆𝑖 , intra-cell degree 𝑑, inter-cell degree 𝑙 Output: grid-based graph index 𝐺 /* Attribute partitioning */ 1 for (𝑖 = 0; 𝑖 < 𝑝; 𝑖 + +) do 2 Sort 𝑜.𝑎𝑖 in ascending order; 3 Partition {𝑜 1, ..., 𝑜𝑛 } into 𝑆𝑖 similar-size segments; 4 Distribute {𝑜 1 , ..., 𝑜 𝑛 } to the corresponding cell; 5 𝐺 ← ∅; // Initialize the index /* Construct intra-cell edges */ 6 for (𝑖 = 0; 𝑖 < 𝑆; 𝑖 + +) do 7 𝐺𝑖 ← Construct the CAGRA index on cell 𝐶𝑖 ; 8 for 𝑜 ∈ 𝐶𝑖 do 9 𝐺 [𝑜].𝑖𝑛𝑡𝑟𝑎 ← 𝐺𝑖 [𝑜]; /* Construct inter-cell edges */ 10 for 𝑜 ∈ D in parallel do 11 for (𝑖 = 0; 𝑖 < 𝑆; 𝑖 + +) do 12 𝐺 [𝑜].𝑖𝑛𝑡𝑒𝑟 [𝑖] ← top-𝑙 ANN of 𝑜 from 𝐺𝑖 ; 13 return 𝐺

computations on out-of-range nodes, severely degrading overall performance. Moreover, to ensure sufficient top-𝑘 results after filtering, it is required to retrieve substantial candidates during the vanilla ANNS, further hindering the high performance.

3

Grid-based Multi-graph Index

In this section, we present the structure of the proposed grid-based multi-graph index within the Garfield framework. Subsequently, we provide an analysis of the index’s time and space complexity.

3.1

Index Structure

Existing RFANNS indexes typically adhere to a common paradigm: partitioning datasets by attribute values into hierarchical tree nodes and constructing a graph index within each node, often resulting in overlapping data coverage across the hierarchy. This redundant indexing is the primary source of index inflation observed in segment-tree and KD-tree-based structures. Moreover, hierarchical tree traversals are inherently incompatible with GPU architectures, inevitably leading to warp divergence and hardware underutilization. Although UNIFY [29] adopts a non-hierarchical structure, it necessitates an excessive number of cross-segment edges and lacks native support for multi-attribute conjunctions. To overcome these limitations, Garfield introduces a grid-based multi-graph (GMG) index, which organizes the dataset into a disjoint, non-hierarchical structure. This design enables efficient multiattribute range-filtered navigation while avoiding the overhead of query-time graph assembly. Specifically, the dataset is partitioned into 𝑆 disjoint segments (referred to as cells), denoted as {𝐶 1, 𝐶 2, ..., 𝐶𝑆 }. Each object 𝑜 is deterministically assigned to exactly one cell based on its numeric attributes 𝐴. To guarantee stable query performance and balanced computational workloads, GMG employs a cardinality-balanced quantile strategy. This strategy is applied to a selected subset of 𝑝 attributes (𝑝 ≤ 𝑚). For each selected 𝑖-th attribute, objects are sorted and evenly divided into 𝑆𝑖 segments of similar size, ensuring the total number of cells is Î𝑝 (𝑆 = 𝑖 𝑆𝑖 ). If an object falls into the 𝑠 1, 𝑠 2, ..., 𝑠𝑝 -th segment across these 𝑝 attribute, it will be positioned to the corresponding coordinate (𝑠 1, 𝑠 2, ..., 𝑠𝑝 ) in the 𝑝-dimensional grid. When the total number of numeric attributes 𝑚 is large, naively partitioning the attribute space across all 𝑚 attributes would generate a prohibitive number of cells. Furthermore, multi-attribute conjunctions frequently result in highly restrictive range filters. Partitioning across all attributes under such high selectivity filtering leads to exponentially inflates space complexity while yielding diminishing returns in search efficiency. Consequently, GMG constructs cells using only the 𝑝 most selective attributes rather than using all 𝑚 attributes. Note that this dimensionality reduction does not degrade Garfield into a postfiltering approach: the 𝑝 partitioned attributes exclusively control the grid segmentation granularity, whereas the full set of 𝑚 query range predicates is still enforced throughout the search procedure. After partitioning the objects into distinct cells, we establish two types of edges to connect the objects. (1) Intra-cell edges. In the GMG index, a cell serves as the fundamental search unit, necessitating sufficient connectivity to navigate queries effectively. Consequently, within each cell 𝐶𝑖 , we construct an independent CAGRA graph 𝐺𝑖 over the local vectors in 𝐶𝑖 . CAGRA [36] is a state-of-the-art

graph index highly optimized for GPU execution. (2) Inter-cell edges. When query ranges span multiple cells, intra-cell edges alone are insufficient to support efficient global search. To maintain cross-cell navigation, inter-cell edges connecting each node to other cells are also required. However, dense inter-cell edges will incur significant storage overhead. To avoid this, Garfield constructs only a minimal set of inter-cell edges. Specifically, each node identifies and connects to its 𝑙 nearest neighbors in every other cell (where the parameter 𝑙 is empirically set to 2).

3.2

Index Construction

The construction process of the GMG index proceeds in three primary steps, as outlined in Algorithm 1. Step 1: Attribute Partitioning. For each of the 𝑝 highly selective attributes, we sort the objects based on the corresponding attribute values and partition them into 𝑆𝑖 segments of similar size (Line 1-3). These objects are subsequently distributed into the 𝑆 distinct cells according to the per-attribute segment assignments (Line 4). Step 2: Intra-cell Edges Construction. Within each cell 𝐶𝑖 , we construct a fix-degree CAGRA index (Lines 6-9). Step 3: Inter-cell Edges Construction. The inter-cell edges are established by querying the local CAGRA index of other cells. To fully utilize GPU parallelism, we batch the object vectors from D and execute a top-𝑙 ANN search for each vector across all other cells in a batched manner on the GPU (Lines 10-12). Example. Consider a dataset comprising ten objects, each associated with two numeric attributes (𝑚 = 2). As illustrated in Figure 2(a), we sort the objects by the first attribute and partition the them into two segments, i.e., [1, 2] and [3, 5]. An identical partitioning strategy is applied to the second attribute. The objects are subsequently distributed among four disjoint cells according to their attribute values. Within each cell, we first construct intra-cell edges 4

[1, 2]

[3, 5]

o1

o1.A={1,1}

[1, 2]

o3

o2.A={2,2} o4

o2

o3.A={3,1}

o5

o4.A={4,2} o5.A={5,2} o6.A={1,3}

o10

o7.A={1,4}

o7

o8.A={2,5}

o9

o9.A={3,4}

o8

o10.A={5,3}

[3, 5] Cell C4

Attribute 2

(2,5)

o7

(1,4)

Intra-cell edges o10 (5,5)

o9

(3,4)

o6

[3, 5]

[1, 2] Cell C3 o8

o8

o9

vector q

(2,2)

(1,1)

filters F #cells ≤ Sthre C1 C2

(1,3)

Cell C2 o4 (4,2)

o3

o5

(5,2)

(3,1)

o2

Selected cells

C3

o5

C4 a1

o3

Top-k Results … Satisfy F and close to q

C2

Top-m clusters for q Estimated distribution

a2

o4

o1

q

(1) Cell Selection

o10

o7

(3) Cell Traversal Search-jump-search paradigm

a1∈[l1,r1] a2∈[l2,r2]

C1 F C2

Cell C1 o2 o1

(2) Cell Ordering

Query Q=(q,F)

Inter-cell edges

o6

[1, 2]

[3, 5]

o6

C1

C2 C1 Ordered cells

Expand entry points by inter-cell edges

Search on the whole graph

C1

C2

Card(C1) < Card(C2)

#cells > Sthre

Attribute 1

(a) Attribute space partitioning.

Figure 3: Overview of the query processing in Garfield.

(b) Grid-based multi-graph index.

Figure 2: Example of attribute partition and index structure. Algorithm 2: Query processing of Garfield Input: dataset D = {𝑜 1, ..., 𝑜𝑛 }, GMG index 𝐺, query 𝑄 = (𝑞, 𝐹 ), number of results 𝑘 Output: top-𝑘 ANN set 𝑅 /* Cell Selection 1 𝐶𝑄 ← ∅; 2 foreach 𝐶𝑖 ∈ cells of 𝐺 in parallel do 3 if 𝐹 intersects 𝐶𝑖 then 4 𝐶𝑄 ← 𝐶𝑄 ∪ {𝐶𝑖 }; 5 if |𝐶𝑄 | > 𝑆𝑡ℎ𝑟𝑒 then 6 𝑅 ′ ← perform ANNS on the whole 𝐺; 7 𝑅 ← top-𝑘 ANN after post-filtering on 𝑅 ′ ; 8 return 𝑅; /* Cell Ordering 9 𝐶𝑄 ← CellOrder(𝐶𝑄 ); /* Cell Traversal 10 𝑅 ← CellTraverse(𝑄, 𝑘); 11 return 𝑅

following the indexing process of CAGRA, assigning each node an out-degree of 1, as depicted in Figure 2(b). To establish the inter-cell edges, each node queries for its top-𝑙 approximate nearest neighbors (𝑙 = 1 in this example) within every other cell. Directed edges are then formed to connect the node to these retrieved neighbors. For visual clarity, Figure 2(b) exclusively displays the inter-cell edges originating from nodes in 𝐶 1 . Space Complexity. As CAGRA is a fixed-degree graph with degree 𝑑 and the cells are disjoint, the intra-cell edges incur a space complexity of 𝑂 (𝑛𝑑), where 𝑛 is the total number of objects. Furthermore, each object maintains 𝑙 inter-cell edges connected to every other cell, resulting in an additional space complexity of 𝑂 (𝑛𝑙𝑆), where 𝑆 is the number of cells. Consequently, the overall space complexity of GMG is 𝑂 (𝑛(𝑑 + 𝑙𝑆)). Construction Complexity. The construction of the GMG index includes three phases. First, attribute partitioning incurs an expected time complexity of 𝑂 (𝑝𝑛 log 𝑛) due to the sorting operations across the 𝑝 attributes. Second, the construction of intra-cell edges comprises NN-Descent and edge pruning, which empirically require 𝑂 (𝑛 1.16 ) [10] and 𝑂 (𝑛𝑑 3 ) [36] time, respectively. Third, establishing the inter-cell edges necessitates querying the local graph index of every other cell. Since each cell contains approximately 𝑛/𝑆 objects on average, a single search takes 𝑂 (log 𝑛𝑆 ) time. Expanding this operation across all 𝑛 objects and 𝑆 cells results in a complexity of 𝑂 (𝑛𝑆 log 𝑛𝑆 ). Summing these components, the overall time complexity is 𝑂 (𝑝𝑛 log 𝑛 + 𝑛 1.16 + 𝑛𝑑 3 + 𝑛𝑆 log 𝑛𝑆 ). Considering 𝑝, 𝑑, and 𝑆 are typically small constants, the construction complexity can be simplified to 𝑂 (𝑛 log 𝑛).

4

*/ */

dynamic assembly process incurs additional runtime overheads and inherently mismatches the coalesced memory access patterns preferred by GPU architectures. Consequently, this paradigm is incompatible with the lightweight design of the GMG index. To address these bottlenecks, we propose a novel multi-cell traversal algorithm tailored for GMG on the GPU. Unlike prior RFANNS methods, Garfield maintains a memory layout for static intra-cell and inter-cell adjacency lists. The fixed structure facilitates predictable memory access and stable GPU throughput. Specifically, given a query 𝑄 = (𝑞, 𝐹 ), Garfield performs RFANNS in three stages, as outlined in Algorithm 2 and illustrated in Figure 3. (1) Cell Selection. Garfield first identifies the cells that intersect with the range predicate 𝐹 . Given that the cells are disjoint and defined by multi-dimensional boundaries, this step is efficiently implemented as a parallel predicate evaluation across all cells. The output is a set of cell IDs 𝐶𝑄 = {𝐶𝑖 |𝐶𝑖 ∩𝐹 ≠ ∅}, where the cardinality |𝐶𝑄 | varies across queries depending on selectivity (Lines 2-4). (2) Cell Ordering. The traversal order of the selected cells significantly impacts both search convergence and traversal overhead. Specifically, Garfield sequentially processes the selected cells, leveraging intermediate results to provide entry points for the subsequent cell via inter-cell edges (detailed below). Intuitively, prioritizing cells that are more likely to contain the true nearest neighbors of 𝑄 yields higher-quality entry points. Consequently, Garfield ranks

Efficient Query Processing on GPUs

In this section, we detail the efficient query processing pipeline executed on GPUs utilizing the proposed GMG index. Subsequently, we present a theoretical analysis of the query time complexity and discuss the optimal number of cells.

4.1

*/

Overview of the Query Pipeline

As discussed in Section 1, existing state-of-the-art RFANNS methods rely on dynamic graph assembly to serve the incoming queries. Typically, these approaches identify segments that satisfy the query’s range predicates and dynamically assemble the corresponding graph indexes, either before or during search execution. However, this paradigm suffers from two limitations. (1) It requires substantial inter-cell edges (several times in scale to the intra-cell edges) to ensure efficient navigation across the assembled graph. (2) The 5

counts

C4

C4

k-means on the whole dataset

card(C4) = 10

Ordered cells: {C4, C3, C2}

C3

cs1 cs2cs3cs4 cs5

C4

C4

counts

cs1 cs2 cs3 cs4 cs5

cs1cs2cs3cs4 cs5

C3 counts

3

cs1 cs2 cs3 cs4 cs5

Offline Preprocessing

…

counts

queries

1 2 3 4 Algorithm 3: CellOrder Input: selected cells 𝐶𝑄 , query vector 𝑞, clusters 𝐶𝑆 Output: ordered cells 𝐶𝑄 1 Compute dist(q, centroids) on Tensor cores; 2 𝑇𝑜𝑝𝐶𝑙𝑢𝑠𝑡𝑒𝑟 ← top-𝑚 clusters with smallest distances to 𝑞; 3 foreach 𝐶𝑖 ∈ 𝐶𝑄 in parallel at warp level do 4 foreach 𝑐𝑠 ∈ 𝑇𝑜𝑝𝐶𝑙𝑢𝑠𝑡𝑒𝑟 in parallel at thread level do 5 𝐶𝑎𝑟𝑑 (𝐶𝑖 ) ← 𝐶𝑎𝑟𝑑 (𝐶𝑖 ) + 𝐻 [𝐶𝑖 , 𝑐𝑠]; 6 Sort 𝐶𝑄 by 𝐶𝑎𝑟𝑑 (𝐶𝑖 ) in descending order; 7 return 𝐶𝑄

centroids

×

cs2 cs1 cs4 …

0.7 0.8 0.9 …

top-m

cs1 cs2 cs3 cs4 cs5 CQ={C1, C2}

counts

k-means clustering

C2

cs cs cs cs cs5

Online Ordering Accelerated by Tensor Cores dis(q, centroids)

C1

C1

Card(C1) = 9

cs1 cs2 cs3 cs4 cs5

counts

C3

C2

Card(C2) = 11

cs1 cs2 cs3 cs4 cs5 Stored into H [Ci, csj]

Ordered cells: {C2, C1}

clusters. Specifically, during offline preprocessing, we perform 𝑘means clustering on the entire dataset to group proximate vectors, as illustrated in Figure 4. For each cell 𝐶𝑖 , we count the number of vectors that belong to the 𝑗-th cluster 𝑐𝑠 𝑗 , storing this frequency in a 2D histogram array 𝐻 [𝐶𝑖 , 𝑐𝑠 𝑗 ]. This histogram acts as a discrete representation of the local data distribution within each cell. During online query processing (right of the Figure 4), we first compute the distances between the query vector and the cluster centroids, subsequently selecting the top-𝑚 nearest clusters. For each selected cell 𝐶𝑖 ∈ 𝐶𝑄 , we estimate its query-aware cardinality by summing the precomputed vector counts corresponding to these top-𝑚 clusters, i.e., Σ𝑐𝑠 ∈𝑇 𝑜𝑝𝐶𝑙𝑢𝑠𝑡𝑒𝑟𝑠 𝐻 [𝐶𝑖 , 𝑐𝑠]. The calculated number of vectors serves as the estimated result cardinality for the cell. Finally, the selected cells in 𝐶𝑄 are sorted in descending order based on these estimations. Following the hardware-software co-design methodology, this estimation pipeline is optimized for GPUs to ensure efficient execution. As shown in Algorithm 3, to mitigate the overhead of online ordering, we leverage GPU Tensor Cores to accelerate the dense matrix multiplications required for query-centroid distance computations (Line 1). The computed distances are then sorted using the bitonic sort [9] to identify the top-𝑚 nearest clusters (Line 2). To evaluate the cardinality of a cell, we assign the task to a dedicated GPU warp. Each thread within the warp concurrently fetches the vector counts from the histogram array 𝐻 for the corresponding clusters, and the threads collaboratively compute the final sum using warp-level reduction primitives (Lines 3-5). Finally, we rank the cells in 𝐶𝑄 based on their estimated cardinalities (Line 6).

Figure 4: Pipeline of cluster-based cell ordering. the selected cells using a GPU-friendly ordering strategy guided by a cluster-based cardinality estimator (Line 9, Section 4.2). (3) Cell Traversal. Garfield then iteratively searches the selected cells following the optimized sequence. Within each cell, it executes a greedy graph traversal while enforcing the range predicate. Upon completing the search within a cell, it utilizes the current candidate pool to traverse the inter-cell edges and generate entry points for the next cell, rather than starting from random entries. This search–jump–search paradigm continues until all selected cells are exhausted (Line 10, Section 4.3). Moreover, to efficiently handle queries with high range selectivity (i.e., when a massive portion of the dataset satisfies the filters), Garfield incorporates an adaptive execution path. Specifically, if the number of selected cells |𝐶𝑄 | exceeds a predefined threshold 𝑆𝑡ℎ𝑟𝑒 , it bypasses the search-jump-search paradigm and directly executes a global greedy traversal across the entire graph index (Lines 5-8). This adaptive design guarantees robust and efficient performance across arbitrary selectivity.

4.2

Cluster-based Cell Ordering

During cell traversal, Garfield utilizes the intermediate results and inter-cell edges to expand the entry points for the subsequent cell. Intuitively, higher-quality intermediate results can lead to entry points that are closer to the true ANNs. To maximize the probability that early-visited cells contribute high-quality candidates, we introduce a cell ordering mechanism before the traversal phase. A simple approach would be to rank the selected cells based on their estimated result cardinality for a given query. However, efficiently estimating the cell’s cardinality with respect to the given query is non-trivial. The distribution of high-dimensional vectors within each cell varies with the datasets and is difficult to characterize. Furthermore, since the baseline cell traversal on the GPU is already fast, any estimation mechanism must be lightweight to avoid becoming a new computational bottleneck. Exact estimation is unnecessary, as long as the estimator merely captures the relative cardinality rankings among cells. To address these issues, we design a cluster-based cardinality estimator tailored to estimate the distribution of the top-𝑘 nearest neighbors across the cells. Unlike traditional estimators designed for low-dimensional data [14, 22] or rigorous but inefficient estimators for high-dimensional data [24], we model the distribution by

4.3

Sequential Cell Traversal

As discussed in Section 2.2, existing RFANNS methods dynamically assemble the graphs from selected cells before or during the traversal. This search paradigm is inherently unfriendly to GPUs, which incurs uncoalesced memory access and warp divergence when retrieving the edges. Moreover, to minimize the index footprint, the GMG index establishes a small number of inter-cell edges. Assembling the graphs of a few cells and traversing the loosely connected assembly graph would degrade search recall. To address these limitations, we design a GPU-friendly, sequential graph traversal paradigm tailored for the GMG index. Garfiled traverses the local graph of each cell sequentially instead of dynamically assembling them. The inter-cell edges are utilized to provide high-quality entry points to the subsequent cell, rather than navigating the traversal. Specifically, Garfield processes 6

O

Algorithm 4: CellTraverse Input: GMG index 𝐺, query 𝑄 = (𝑞, 𝐹 ), ordered cells 𝐶𝑄 , intra-degree 𝑑, inter-degree 𝑙, 𝑘 Output: top−𝑘 ANN set 𝑅 1 𝐶𝑎𝑛𝑑 ← randomly select 𝑑 nodes, 𝑟𝑒𝑐𝐶𝑎𝑛𝑑 ← ∅, 𝑅 ← ∅; 2 foreach 𝐶𝑖 ∈ 𝐶𝑄 do 3 Calculate 𝑑𝑖𝑠 (𝑞, 𝑣) where 𝑣 ∈ 𝐶𝑎𝑛𝑑 in parallel; 4 while |𝐶𝑎𝑛𝑑 | > 0 do 5 𝑢 ← pop the nearest unvisited neighbor in 𝐶𝑎𝑛𝑑; 6 foreach unvisited 𝑣 ∈ 𝐺 [𝑢].𝑖𝑛𝑡𝑟𝑎 in parallel do 7 mark 𝑣 as visited; 8 𝑧 ← the furthest neighbor to 𝑞 in 𝑅; 9 if 𝑑𝑖𝑠 (𝑞, 𝑣) < 𝑑𝑖𝑠 (𝑞, 𝑧) then 10 𝐶𝑎𝑛𝑑 ← 𝐶𝑎𝑛𝑑 ∪ {𝑣 }, push 𝑣 to 𝑅; 11 if |𝑅| > 𝑘 then 12 pop the furthest node 𝑤 from 𝑅; 13 push 𝑤 to 𝑟𝑒𝑐𝐶𝑎𝑛𝑑 if 𝑤 satisfies 𝐹 ; 14 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦 ← random select 𝑑 nodes in 𝐶𝑖+1 ; 15 for 𝑣 ∈ the first 𝐿 nodes in 𝐶𝑎𝑛𝑑 do 16 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦 ← 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦 ∪ 𝐺 [𝑣].𝑖𝑛𝑡𝑒𝑟 [𝑖 + 1]; 17 Calculate 𝑑𝑖𝑠 (𝑞, 𝑣) where 𝑣 ∈ 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦 in parallel; 18 𝐶𝑎𝑛𝑑 ← the 𝑑 nearest nodes in 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦 w.r.t 𝑞; 19 foreach 𝑢 ∈ 𝑅 do 20 if 𝑢 doesn’t satisfy 𝐹 then 21 pop 𝑢 from 𝑅; 22 𝑅 ← the top-𝑘 nearest nodes in 𝑅 ∪ 𝑟𝑒𝑐𝐶𝑎𝑛𝑑 w.r.t. 𝑞; 23 return 𝑅

of 𝑅 exceeds 𝑘, the furthest node is popped. If this node satisfies the range predicates 𝐹 , it is added to 𝑟𝑒𝑐𝐶𝑎𝑛𝑑 (Lines 11-13). Upon completing the traversal of a cell, Garfield fills the 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦 with inter-cell neighbors of the current candidates alongside random nodes from the next cell (Lines 14-16). The nearest nodes from 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦 are then selected as the entry points for the graph of the subsequent cell (Lines 17-18). The candidate pool 𝐶𝑎𝑛𝑑 and result set 𝑅 are maintained throughout the traversal process, avoiding additional merging overhead and ensuring efficient convergence on subsequent cells. Once all selected cells are traversed, Garfield filters the ANN in 𝑅 against the predicates 𝐹 and supplements 𝑅 with nodes in 𝑟𝑒𝑐𝐶𝑎𝑛𝑑 to produce the final results (Lines 19-22).

4.4

Theoretical Analysis

In this subsection, we analyze the time complexity of Garfield’s query processing and mathematically discuss the optimal number of cells to maximize search efficiency. For the traversal of the initial cell, the expected time complexity is 𝑂 (log(𝑛/𝑆)), where 𝑛 is the size of the dataset and 𝑆 is the number of cells. For subsequent cells, the entry points expanded by inter-cell edges can reduce the time complexity to 𝑂 (𝛼 log(𝑛/𝑆)), where 𝛼 ∈ (0, 1). Given a query range selectivity of 𝜎 (𝜎 ∈ [0, 1]), the expected number of cells intersecting the query is 𝜎𝑆. Therefore, the expected time complexity for query processing is 𝑂 ((1 + 𝜎𝑆𝛼) log 𝑛/𝑆). To investigate the impact of 𝑆 on query efficiency, we model the query time complexity as a continuous function of 𝑆: 𝑇 (𝑆) = (1 + 𝜎𝑆𝛼) log 𝑛/𝑆. To analyze the trend of 𝑇 (𝑆) with respect to 𝑆, we take its derivative in Equation 1. 𝑛 1 𝑑𝑇 = 𝜎𝛼 (log − 1) − (1) 𝑑𝑆 𝑆 𝑆 Assuming each cell contains a sufficient number of objects (e.g., 𝑛/𝑆 ≥ 4), 𝑇 (𝑆) initially decreases and subsequently increases w.r.t 𝑆, exhibiting a convex trend within the valid 𝑆 ∈ [1, 𝑛/4]. Consequently, we can locate its local minimum by setting the derivative to zero: 1 1 𝑆= · (2) 𝜎 𝛼 (log 𝑛/𝑆 − 1) To analyze the macroscopic relationship between query efficiency and 𝑆, we observe that the dataset volume 𝑛 is typically orders of magnitude larger than 𝑆 (𝑛 ≫ 𝑆). Because the logarithmic term varies extremely slowly compared to linear terms, we can safely approximate the inverse term [𝛼 (log(𝑛/𝑆) − 1)] −1 as a datasetdependent constant 𝜃 . Substituting this results in a simplified condition: 𝑆 ≈ 𝜃 /𝜎. This reveals that the optimal number of cells 𝑆 is inversely proportional to the query selectivity 𝜎, i.e., 𝑆 ∝ 1/𝜎. Intuitively, if 𝑆 < 𝜃 /𝜎 (too few cells), the selected cell will include substantial out-of-range objects, leading to redundant distance computations. Conversely, if 𝑆 > 𝜃 /𝜎 (too many cells), although the out-of-range overhead is minimized, the overhead of transitioning between excessively fragmented subgraphs dominates and decreases the query performance.

the cells sequentially following the optimized order generated by CellOrder (Algorithm 3). While the search within the initial cell begins from randomly sampled nodes, the entry points for the subsequent graphs are expanded using the current results retrieved from previously visited cells. To achieve this, Garfield maintains a global candidate pool to store the current nearest neighbors discovered so far. Upon completing the traversal of cell 𝐶𝑖 and transitioning to cell 𝐶 𝑗 , the system collects the neighbors of the current candidates via the inter-cell edges connected to the nodes in 𝐶 𝑗 , storing them in a set 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦. To mitigate the risk of low-quality entry points, we also randomly generate a few entry points to augment 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦. Garfield then evaluates the distances between the query and the nodes in 𝐶𝑎𝑛𝑑𝐸𝑛𝑡𝑟𝑦, selecting the closest nodes as the entry points. The introduction of inter-edge based entry point selection eliminates the need to search each subgraph from scratch, effectively accelerating convergence and overall search efficiency. The traversal pipeline of Garfield is formalized in Algorithm 4. Garfield initializes the global candidate pool with 𝑑 random nodes from the first cell. It also employs a recycle pool 𝑟𝑒𝑐𝐶𝑎𝑛𝑑 to retain discarded nodes from the candidate pool satisfying the range predicates 𝐹 (Line 1). For each cell 𝐶𝑖 , Garfield first evaluates the distances between the query 𝑞 and the nodes in 𝐶𝑎𝑛𝑑. To maximize GPU utilization, each warp is assigned the task of computing the distance between a node 𝑣 and 𝑞 (Line 3). During the greedy traversal, Garfield iteratively extracts the nearest unvisited neighbor from 𝐶𝑎𝑛𝑑, explores its intra-cell neighbors, and expands the closer neighbors into 𝐶𝑎𝑛𝑑 and the result set 𝑅 (Lines 5-10). If the capacity

5

Out-of-core RFANNS

Unlike CPU-based systems backed by large DRAM, GPU execution is constrained by limited on-device memory. This section details how Garfield scales to datasets that exceed GPU memory limits. 7

CPU 1

4

Selecting Cells

CUDA Memcpy Re-ranking Results 3 2 Scheduling Cells Collecting Index 7

Partial Index

GPU 6

Computing Distances using Quantized Vectors

Quantized Vectors

Traversing the Index for Each Cell

Index Buffers

Results ID 5

Metadata of Each Cell

Original Vectors

GMG Index

CPU Transfer Batch 0 GPU

Transfer Batch 1

Re-rank Batch n-1

Batch 0

Batch 1

C0

C1

C3

C2

C3

q0 q1 q2 q3 Active = 4

Active = 4

Active = 2

Active = 2

4 Blocks on the GPU

4 Blocks on the GPU

2 Blocks on the GPU

2 Blocks on the GPU

Re-rank Batch n

Transfer Transfer Compute Batch 0 Compute Batch 1 … Compute Batch n Results Results

(b) Query processing pipeline between the CPU and the GPU.

(a) Dispatch cells in the original order. (b) Dispatch cells in the optimal order.

Figure 5: Pipeline of out-of-core RFANNS in Garfield.

5.1

Batch 1 C2

C1

q0 q1 q2 q3

(a) Out-of-core RFANNS workflow for large-scale datasets. Re-rank Batch 0 … Transfer Batch 2

Batch 0 C0

Figure 6: Comparison of different cell scheduling strategies.

Pipeline for Large-scale RFANNS

The cell-by-cell query processing paradigm of the GMG index is inherently well-suited for out-of-core execution, as cells can be streamed to the GPU in batches. Nonetheless, designing an optimal execution workflow remains non-trivial due to the PCIe I/O overhead between the GPU and CPU. In Garfield, the CPU DRAM stores the original vectors, the complete GMG index, and the metadata of cells (e.g., boundaries). The GPU HBM stores only the quantized vectors, adhering to standard practices existing studies [21, 43]. Moreover, the computationintensive graph traversal and distance calculations are accelerated by the GPU, while the lightweight exact distance verification and batch scheduling are executed on the CPU. As shown in Figure 5(a), 1 identifies the cells for a given query 𝑄 = (𝑞, 𝐹 ), Garfield first ○ (𝐶𝑄 ) intersecting with the range predicates 𝐹 on the CPU. Next, 2 dispatches these cells into balanced a lightweight scheduler ○ batches for GPU execution (detailed in Section 5.2). Subsequently, 3 gathers the required index for each cell in a batch. For the CPU ○ example, if a batch comprises {𝐶𝑖 , 𝐶 𝑗 , 𝐶𝑘 }, Garfield extracts their respective intra-cell edges alongside the inter-cell edges between 4 transferred to the GPU. them. This extracted partial index is then ○ 5 initiates a traversal Upon receiving the batch data, the GPU ○ 6 computes the distances using the over the partial index, and ○ resident quantized vectors. After the traversal, the IDs of the top-𝑘 candidates from this batch are transferred back to the CPU. Finally, 7 re-ranks these candidates using the original vectors the CPU ○ and merges them into the global result set. To mitigate the data transfer overhead, Garfield employs a pipelining strategy that overlaps GPU computation with CPU-to-GPU index streaming. As depicted in Figure 5(b), while the GPU is executing the search for the current batch, the CPU concurrently streams the partial index for the subsequent batch over PCIe. This overlap of I/O and computation forms a highly efficient pipeline that reduces overall latency. Furthermore, the CPU re-ranking phase is deeply integrated into this asynchronous pipeline. Because managing PCIe data transfers requires a single CPU thread, the remaining CPU cores are dedicated to computing the exact distances for the retrieved candidates. Although a majority of vectors are filtered by the GPU, re-ranking the surviving candidates remains a computationintensive task. Consequently, we allocate multiple threads to parallelize the re-ranking operation. Ultimately, the overlap of index streaming, GPU traversal, and CPU re-ranking effectively reduces the overall latency for RFANNS on large-scale datasets, achieving efficient collaboration between CPU and GPU.

Algorithm 5: Cell scheduling in Garfield Input: query set 𝑄 with 𝑚 queries, cell set 𝐶 with 𝑛 cells, incidence matrix 𝐴, bath size 𝑏 Output: optimized batches 𝐵 1 𝐵 1 , 𝐵 2 , ..., 𝐵 ⌈𝑛/𝑏 ⌉ ← ∅, 𝐵 ← {𝐵 1 , 𝐵 2 , ..., 𝐵 ⌈𝑛/𝑏 ⌉ }; 2 foreach 𝐶 𝑗 in 𝐶 do 3 𝑚𝑖𝑛𝐴𝑐𝑡 ← 𝑖𝑛𝑓 , 𝑚𝑖𝑛𝐼𝐷 ← −1; 4 foreach 𝐵𝑘 ∈ 𝐵 do 5 if |𝐵𝑘 | < 𝑏 then 6 𝑐𝑢𝑟𝐴𝑐𝑡 ← 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵𝑘 ∪ {𝐶 𝑗 }) − 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵𝑘 ); 7 if (𝑐𝑢𝑟𝐴𝑐𝑡 < 𝑚𝑖𝑛𝐴𝑐𝑡) or (𝑐𝑢𝑟𝐴𝑐𝑡 = 𝑚𝑖𝑛𝐴𝑐𝑡 ∧ 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵𝑘 ) < 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵𝑚𝑖𝑛𝐼 𝐷 )) then 8 𝑚𝑖𝑛𝐴𝑐𝑡 ← 𝑐𝑢𝑟𝐴𝑐𝑡, 𝑚𝑖𝑛𝐼𝐷 ← 𝑘; 9 𝐵𝑚𝑖𝑛𝐼 𝐷 ← 𝐵𝑚𝑖𝑛𝐼 𝐷 ∪ {𝐶 𝑗 }; 10 return 𝐵

5.2

Cell-oriented Scheduling

Due to the variable nature of multi-attribute query ranges, the number of cells required per query varies. Naively dispatching cells to the GPU leads to severe workload imbalance and heavy contention for memory bandwidth and registers, ultimately degrading overall query throughput. Consider the motivating example in Figure 6(a), suppose there are 4 cells and 4 queries, with each batch including 2 cells. Queries 𝑞 0 and 𝑞 1 target cells 𝐶 0 and 𝐶 2 , whereas queries 𝑞 2 and 𝑞 3 target 𝐶 1 and 𝐶 3 . If cells are dispatched in the original order (i.e., {𝐶 0, 𝐶 1 } in Batch 0 and {𝐶 2, 𝐶 3 } in Batch 1), all four queries become active in both batches. Because Garfield assigns each active query to a dedicated GPU thread block, this naive schedule requires 4 thread blocks per batch. In real-world high concurrency scenarios, the number of active queries easily exceeds the available GPU streaming multiprocessors (SMs), leading to massive thread block dispatching and prohibitive context-switching overheads. To resolve this bottleneck, Garfield introduces a heuristic cell scheduler following the identification of intersected cells (Step 2 in Figure 5(a)). As illustrated in Figure 6(b), regrouping 𝐶 0 with 𝐶 2 into Batch 0, and 𝐶 1 with 𝐶 3 into Batch 1 reduces the number of active queries to two per batch. This optimized schedule reduces the required blocks, alleviating GPU compute and memory contention. Formally, the objective of cell scheduling is to partition the cells into batches such that the number of active queries across all batches is minimized. Given a query set 𝑄 = {𝑞 1, 𝑞 2, ..., 𝑞𝑚 } 8

Table 1: Details of Datasets.

and cell set 𝐶 = {𝐶 1, 𝐶 2, ..., 𝐶𝑛 }, we divide the cells into batches 𝐵 = {𝐵 1, 𝐵 2, ..., 𝐵 ⌈𝑛/𝑏 ⌉ }, with each batch bounded by a capacity of 𝑏 cells. We construct a query-cell incidence matrix 𝐴 ∈ {0, 1}𝑚×𝑛 , where 𝐴𝑖 𝑗 = 1 if query 𝑞𝑖 requires searching cell 𝐶 𝑗 , and 𝐴𝑖 𝑗 = 0 otherwise. A query 𝑞𝑖 is considered active in batch 𝐵𝑘 if it accesses at least one cell within that batch. Thus, the number of active queries in 𝐵𝑘 is defined using an indicator function I(·): 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵𝑘 ) = Σ𝑚 𝑖=1 I(Σ𝐶 𝑗 ∈𝐵𝑘 𝐴𝑖 𝑗 ≥ 1). We formulate this scheduling task as an optimization problem aimed at finding an optimal batch partition 𝐵 ∗ as depicted in Equation 3. ∑︁ 𝐵 ∗ = arg min 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵𝑘 ) (3) 𝐵

#Base

#Query

Attributes

Deep1M SIFT1M

96 128

1,000,000 1,000,000

1,000 1,000

DBLP

768

1,000,000

1,000

YouTube

1024

1,000,000

1,000

Uniform random Uniform random Year, #authors, #references, #citations Year, time, #views, #likes Uniform random Uniform random

𝐵𝑘 ∈𝐵

(3) iRangeGraph [52] is a state-of-the-art method optimized for single-attribute RFANNS. It supports multi-attribute RFANNS by constructing an index on a primary attribute and visiting the outof-range neighbors with a predefined probability. (4) UNIFY [29] is another state-of-the-art method for single-attribute RFANNS. We extend it to support multi-attribute RFANNS by building an index on an attribute and employing the post-filtering strategy to derive the final results. (5) GPU-Pre is our custom GPU baseline implementation. It executes an exact pre-filtering step, followed by a brute-force linear scan over the valid subset to compute the exact nearest neighbors. (6) CAGRA-Post is our second custom GPU baseline. It first performs vanilla ANNS using the state-of-the-art GPU-based index CAGRA [36] and subsequently leverages the post-filtering strategy to derive the final results on the GPU. Parameters.The parameters 𝑀, 𝑑, and 𝐸𝐹 denote the maximum graph degree, fixed degree, and the size of the candidate pool during index construction, respectively. For datasets other than DBLP and YouTube, we set 𝑀 = 16, 𝑑 = 16, and 𝐸𝐹 = 100. For DBLP and YouTube, these are set to 𝑀 = 32, 𝑑 = 32, and 𝐸𝐹 = 200. For ACORN, we configure 𝑀 = 32 and deploy the ACORN-1 variant. The number of cells 𝑆 is set to 16 for UNIFY and Garfield on 1Mscale datasets, and 36 for 100M-scale datasets. We fix the CPU thread count at 10 for both index construction and query processing. Metrics. We evaluate query accuracy using Recall and measure search throughput via Queries Per Second (QPS). Queries are executed in batches, and the QPS is derived from the total end-to-end latency across all queries. Platforms. All experiments are conducted on an Ubuntu 24.04 server, featuring an Intel Core i9-10900K [email protected], 128GB RAM, and an NVIDIA GeForce RTX 3090 GPU (24GB). Garfield is implemented in C++/CUDA under CUDA 12.0.

Experiments

In this section, we conduct comprehensive evaluations of Garfield against existing state-of-the-art RFANNS methods.

6.1

Dim.

Deep100M 96 100,000,000 10,000 SIFT100M 128 100,000,000 10,000

Since cell scheduling is an online process, its efficiency directly affects the overall query latency. Consequently, Garfield designs a heuristic greedy algorithm. The core intuition is to iteratively assign each cell to the batch that leads to the minimal increase in active queries. As outlined in Algorithm 5, we initially configure 𝐵 1, ..., 𝐵 ⌈𝑛/𝑏 ⌉ as empty batches (Line 1). Subsequently, we incrementally map each cell 𝐶 𝑗 ∈ 𝐶 into a batch. For a given cell, the algorithm evaluates all the batches with size less than 𝑏 and computes the number of active queries if the cell were inserted (Lines 4-8). The cell is then permanently assigned to the specific batch that incurs the smallest incremental cost in active queries (Line 9). Example. Consider the execution of Algorithm 3 on the scenario from Figure 6(b). Initially, both batches are empty. The first cell, 𝐶 0 , is assigned to the first batch 𝐵 0 . For 𝐶 1 , we have 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵 0 ∪{𝐶 1 }) = 4, whereas 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵 1 ∪ {𝐶 1 }) = 2. Since placing 𝐶 1 results in a lower number of active queries, 𝐶 1 is assigned to 𝐵 1 . Next, for 𝐶 2 , 𝐴𝑐𝑡𝑖𝑣𝑒 (𝐵 0 ∪ {𝐶 2 }) = 2, whereas adding it to 𝐵 1 increases 𝐵 1 ’s active queries to 4. Thus, 𝐶 2 is optimally inserted into 𝐵 0 . Finally, 𝐶 3 is assigned to 𝐵 1 since 𝐵 0 has reached its maximum capacity.

6

Dataset

Experimental Setup

Datasets. We employ 6 datasets for comprehensive evaluations, which are widely used in related works [12, 25, 29, 52]. Because the Deep [6] and SIFT [1] datasets natively contain only vectors, we synthesize a randomly generated integer attribute for each ve ctor, following standard practices [17, 29, 44]. The DBLP [3] and YouTube [2] datasets contain real-world vectors coupled with skewed numeric attributes. To evaluate performance across a diverse filtering range, we assign query range predicates by uniformly generating selectivities between 1% and 100% for each attribute. A detailed statistical summary of all datasets is provided in Table 1. Methods. We evaluate Garfield against 6 open-source baselines spanning both CPU and GPU platforms. (1) ACORN [38] is a predicate-agnostic graph index supporting a wide array of predicates, including label and range filtering. It traverses only neighbors that satisfy the given query filter and expands with two-hop neighbors if the current neighbors are insufficient. (2) Navix [42] is an HNSW-based, predicate-agnostic graph index. It dynamically decides whether to explore all neighbors or only unfiltered neighbors based on query selectivity.

6.2

Overall Performance

We first evaluate the indexing overhead and search performance of all methods across 6 datasets. Table 2 reports the build time and index size for all compared methods. As GPU-Pre doesn’t rely on any index, its statistics are omitted. For large datasets comprising 100M vectors, we omit methods that trigger out-of-memory (OOM) errors during execution. ACORN and Navix are predicate-agnostic methods. ACORN constructs an unpruned HNSW graph, while Navix utilize the standard HNSW index. Consequently, both of them exhibit faster build processes and more compact index sizes than iRangeGraph and UNIFY, which are specifically designed for 9

IP neighbors only

RNG neighbors on

Alan-Poe (full) without keyword edge Alan-Poe (3) without keyword edge

Table 2: Comparison of index build time and index size. OOM denotes "out-of-memory" during index building. Three paths without keyword edges Full-text without keyword edges

Methods ACORN Navix iRangeGraph UNIFY CAGRA-Post Garfield

Deep1M

SIFT1M

DBLP

YouTube

Deep100M

SIFT100M

Deep1M

SIFT1M

DBLP

YouTube

Deep100M

SIFT100M

19.80 33.71 300.06 858.94 9.79 18.75

22.91 40.99 309.61 814.24 9.83 18.91

100.94 770.32 2640.48 3960.98 14.79 127.18

97.59 538.90 2527.44 3179.13 14.82 144.32

OOM 14871.30 OOM OOM OOM 3034.83

OOM 18096.10 OOM OOM OOM 3147.42

442.63 137.58 941.46 2173.31 61.04 183.11

442.63 137.58 862.93 2174.12 61.04 183.11

440.32 256.36 1392.64 4188.16 122.07 244.14

440.32 245.76 710.45 4117.92 122.07 244.14

OOM 13373.44 OOM OOM OOM 33566.72

OOM 13762.56 OOM OOM OOM 33566.72

iRangeGraph

UNIFY

CAGRA-Post

GPU-Pre

1 0 5

1 0 5

1 0 5

1 0 5

1 0 5

4

4

1 0 4

1 0 4

1 0 4

1 0 4

1 0 5

1 0 5

1 0 4

1 0 4

1 0 3

1 0 3 2

2

1 0

0 .6

0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 0

1 .0

0 .6

(g) Deep1M (𝑚 = 2) 1 0 5

1 0 5

1 0 4

1 0 4 1 0 3 2

0 .8 0 .9 R e c a ll@ 1 0

(m) Deep1M (𝑚 = 4)

1 .0

1 0

0 .6

0 .7

0 .8 0 .9 R e c a ll@ 1 0

(n) SIFT1M (𝑚 = 4)

0 .7

0 .8 0 .9 R e c a ll@ 1 0

Q P S

(e) Deep100M (𝑚 = 1)

(f) SIFT100M (𝑚 = 1) 1 0 5

1 0 4

1 0 4

1 0 4

1 0 4

1 0 3 2

0 .6

0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 0 3 2

1 0

1 .0

0 .6

(i) DBLP (𝑚 = 2)

1 .0

Q P S

(d) YouTube (𝑚 = 1)

0 .7

0 .8 0 .9 R e c a ll@ 1 0

(j) YouTube (𝑚 = 2)

1 0 1 0

2

1 0 3 1 0 2

0 .6

0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 .0

(o) DBLP (𝑚 = 4)

1 0

1

0 .5

0 .6

0 .7 0 .8 R e c a ll@ 1 0

0 .9

(p) YouTube (𝑚 = 4)

2

0 .6

0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 .0

1 0 5

1 0 4

1 0 4

1 0 1 0

2

0 .6

0 .7

0 .8 0 .9 R e c a ll@ 1 0

(q) Deep100M (𝑚 = 4)

0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 .0

(l) SIFT100M (𝑚 = 2)

1 0 5

3

1 .0

1 0 3 1 0 2 0 .6

1 .0

(k) Deep100M (𝑚 = 2)

1 0 4 3

1 0 3 1 0

1 .0

1 0 5

1 0 4

2

1 0 2 0 .6

1 .0

R e c a ll@ 1 0

1 0 5

1 0

1 .0

R e c a ll@ 1 0

1 0 3

1 0 5

1 0 5

1 0 3 0 .7

0 .8 0 .9 R e c a ll@ 1 0

Q P S

Q P S

1 0 6

0 .6

0 .7

1 0 3

ThreeRouteGPU 2 1 0 Alan-Poe-ThreePath Allan-Poe-TwoPath 0 .7 0 .8 0 .9 1 .0 0 .6 0 .7 0 .8 0 .9

1 0 5

(h) SIFT1M (𝑚 = 2)

1 0 6

1 0

(c) DBLP (𝑚 = 1)

Q P S

1 0 6

1 0 2 Allan-Poe-text 0 .8 0 .9 1 .0 0 .6 R e c a ll@ 1 0

Q P S

(b) SIFT1M (𝑚 = 1)

1 0 6

1 0 3

Q P S

1 .0

1 0 2 Allan-Poe-sparse 1 .0 0 .6 0 .7

Q P S

0 .8 0 .9 R e c a ll@ 1 0

1 0 3

Q P S

1 0 2 Allan-Poe-dense 0 .6 0 .7 0 .8 0 .9 R e c a ll@ 1 0

Q P S

1 0 3

1 0 2 0 .6

1 0

Q P S

1 0 3

1 0

Q P S

Q P S

1 0 5

Q P S

Q P S

Navix 1 0 6

(a) Deep1M (𝑚 = 1)

Q P S

ACORN

1 0 6

Q P S

Q P S

Garfield 1 0 6

0 .7

Three paths with keyword edges

Full-text Indexwith Sizekeyword (MB) edges

Build Time (s)

1 .0

1 0 3 1 0 2 0 .6

0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 .0

(r) SIFT100M (𝑚 = 4)

Figure 7: Comparison of all methods on 6 real-world datasets. RFANNS. In contrast, although Garfield is also tailored for RFANNS, it maintains an index size comparable to the vanilla HNSW index (i.e., the index of Navix). Furthermore, Garfield reduces index build time by 1.7-5.5× compared to the vanilla HNSW index. This efficiency stems from the lightweight structural design of the GMG index and its highly optimized GPU-accelerated construction pipeline. Compared to the dedicated RFANNS indexes, Garfield’s superiority is even more pronounced, delivering remarkable indexing speedups of 12.0-17.5× over iRangeGraph and 22.0-51.8× speedup over UNIFY. Crucially, this lightweight structure effectively mitigates index inflation, reducing the index size by 2.9-5.1× and 11.9-16.9× compared to iRangeGraph and UNIFY, respectively. While CAGRA-Post (employing the original CAGRA index) exhibits the fastest construction and the smallest index size, its post-filtering strategy limits the query performance, as detailed below. To comprehensively evaluate multi-attribute RFANNS performance, we vary the number of filtering attributes (𝑚) across 1, 2, and 4. As illustrated in Figure 7, Garfield consistently outperforms all the compared methods across all 6 real-world datasets. Specifically, under single-attribute constraints at a target recall of 0.9, Garfield achieves throughput speedups of 77.2-235.8×, 8.0-54.2×, 4.6-32.9×, 10.4-45.3×, and 1.4-2.6× over ACORN, Navix, iRangeGraph, UNIFY, and CAGRA-Post, respectively. On higher-dimensional datasets such as DBLP and YouTube, GPU acceleration becomes increasingly advantageous due to the extensive parallelism applied to

complex distance calculations. As the number of filtering attributes increases, Garfield demonstrates robust scalability owing to its native multi-attribute index architecture. For instance, under twoattributes constraints at a 0.9 recall, Garfield achieves speedups of 23.3-117.9×, 10.9-23.4×, 12.5-153.4×, 13.5-58.1×, and 1.4-5.0× over ACORN, Navix, iRangeGraph, UNIFY, and CAGRA-Post, respectively. Most critically, under four-attribute constraints, the majority of the compared methods completely fail to achieve high recall. This severe degradation occurs because multi-attribute constraints significantly hinder the graph connectivity. In contrast, Garfield leverages the multi-attribute native GMG index, maintaining robust connectivity and high recall under multi-attribute constraints via its inter-cell edges.

6.3

Impact of Selectivity

To evaluate query efficiency under varying query range selectivities, we conduct experiments using query range widths of 1/64, 1/16, and 1/4 across 1, 2, and 4 attributes. As depicted in Figure 8, under a narrow query range (i.e., low query selectivity), Garfield exhibits superior performance compared to CAGRA-Post. Conversely, Garfield demonstrates increasing speedups over GPU-Pre as the query range width expands. This indicates that neither post-filtering nor pre-filtering strategies can consistently maintain high performance across various selectivities, underscoring the necessity of a 10

Garfield on four-attribute index

Garfield on dedicated index

Garfield

ACORN Navix CAGRA-Post

iRangeGraph GPU-Pre

1 0 6

1 0 6

1 0 6

1 0 5

1 0 5

1 0 4 1 0 3 0 .6 0 .8 R e c a ll@ 1 0

1 .0

1 0 5

1 0 4

1 0 4

1 0 4

1 0 4

1 0 3

1 0 3

1 0 2 0 .4

1 0 2 0 .4

0 .6 0 .8 R e c a ll@ 1 0

2

1 0 5

1 0 6

1 0 4

1 0 4

1 0 4

1 0 5

1 0 3

1 0 3

1 0 3

1 0 4

1 0 2 0 .4

1 0 2 0 .4 1 .0

1 0 2 1 .0 0 .4

(e) 𝜎 = 1/16, 𝑚 = 2 1 0

1 0 5

1 0 5

1 0 4

1 0 4

1 0 4

1 0 3

1 0 3

1 0 3

(g) 𝜎 = 1/64, 𝑚 = 4

1 .0

1 0 2 0 .4

0 .6 0 .8 R e c a ll@ 1 0

(h) 𝜎 = 1/16, 𝑚 = 4

1 .0

2

1 0 2 0 .4

4

6

8

1 0

Garfield

ACORN

UNIFY

CAGRA

m

(b) SIFT1M, 0.9 recall

1 0 5

S=8

S = 16

S = 24

S = 36

4

6 8 1 0 iRangeGraph m

1 0 4 1 0 3

2

1 0

2 4 Garfield

6

1 0 2

8 1 0 ACORN

m

2 Navix

(c) Deep1M, 0.95 recall

UNIFY

CA

(d) SIFT1M, 0.95 recall

Figure 9: Impact of variousl =numbers 1 l = 2of filtered l = 4 attributes. l=8 0 .6 0 .8 R e c a ll@ 1 0

1 attribute RFANNS on dedicated index

1 .0

1 0

6

(i) 𝜎 = 1/4, 𝑚 = 4 Q P S

Figure 8: Impact of various selectivities on DBLP dataset. dedicated index for RFANNS. Although the CPU-based baselines perform relatively stably across different selectivities, Garfield still consistently outperforms them. With different selectivities, Garfield achieves speedups of 96.6×, 20.2×, 22.6×, and 22.3× over ACORN, Navix, iRangeGraph, and UNIFY on average, respectively. These results demonstrate the robust query efficiency of Garfield across variable selectivities and different numbers of attributes.

6.4

1 0 2

1 0

1 0 3

1 .0

CAGRA-Post

1 0 6

6

1 0 5

0 .6 0 .8 R e c a ll@ 1 0

0 .6 0 .8 R e c a ll@ 1 0

(f) 𝜎 = 1/4, 𝑚 = 2

6

8

(a) Deep1M, 0.9 recall

1 0 5

1 0 2 0 .4

6

(c) 𝜎 = 1/4, 𝑚 = 1

1 0 5

1 0

4 m

1 0 6

0 .6 0 .8 R e c a ll@ 1 0

UNIFY

1 0 3

1 0 2

1 .0

Q P S

Q P S

1 .0

1 0 3

(b) 𝜎 = 1/16, 𝑚 = 1

(d) 𝜎 = 1/64, 𝑚 = 2

Q P S

0 .6 0 .8 R e c a ll@ 1 0

Q P S

1 0 5

1 0 6

1 0

iRangeGraph

1 0 5

(a) 𝜎 = 1/64, 𝑚 = 1

6

Navix

1 0 6

1 0 6

0 .6 0 .8 R e c a ll@ 1 0

ACORN

1 0 6

1 0 5

1 0 4 0 .7

1 attribute RFANNS on four-attribute index

Allan-Poe-dense

1 attribute RFANNS on four-attribute index

w/ Pipeline (m=1) w/ Pipeline (m=1)

0 .8

2 attribute RFANNS on dedicated index

Allan-Poe-sparse 1 0 6 1 attribute RFANNS on dedicated index

Q P S

1 0 2 0 .4

Garfield

Q P S

Q P S

UNIFY

Q P S

Garfield

w/o Pipeline (m=1)

0 .9

R e c a l l @ w/ 1 0 Ordering w/ Ordering (m=1) (a) Deep1M (m=2) w/o Ordering w/o Ordering (m=2) (m=1)

1 0 5

w/o Pipeline (m=2)

w/o Pipeline (m=1)

1 .0

2 attribute RFANNS on four-attribute index

2 attribute RFANNS on four-attribute index

w/ Pipeline (m=2)

w/ Pipeline 1 0 4 (m=2)

w/o Pipeline (m=2)

w/ Ordering (m=4) w/o Ordering (m=4)

(b) SIFT1M

0 .7

ThreeRouteGPU Allan-Poe-TwoPath A

Allan-Poe-text

2 attribute RFANNS on dedicated index

w/o Pipeline (m=4) w Pipeline (m=4)

0 .8 0 .9 R e c a ll@ 1 0

1 .0

w/ Pipeline (m=4) w/o Pipeline (m=4)

Figure 10: Performance of RFANNS with partial attributes filter on the for 4 attributes. w/o Inter-edge w/o Inter-edge w/o index Inter-edge constructed (m=1)

(m=2)

(m=4)

w/ Inter-edge w/ Inter-edge Inter-edge Althoughw/ it recommends choosing the partitioned attributes (m=2) (m=4) (m=1) according to the number of attributes frequently used in range w/ Inter-edge w/ Inter-edge index w/ Inter-edge filters, the resulting remains fully functional when a query (m=2) (m=1) (m=4) w/o Inter-edge Inter-edge attributes. For example, Inter-edge constrains w/o only a subset of thosew/oindexed (m=2) (m=4) (m=1) even if the index is built using 4 attributes, a query may specify range predicates on only 1–2 of them. We evaluate this scenario by running partial-attribute RFANNS queries on an index constructed over all four attributes and comparing against the ideal baseline that rebuilds dedicated indexes using only the attributes that are actually filtered. As depicted in Figure 10, using the full-attribute index incurs a 90% decrease in QPS on average. This overhead is acceptable in practice, given that rebuilding and maintaining separate indexes for every possible subset of filtered attributes is prohibitive. This indicates that GMG is robust to various queries with a single index built once for a superset of filtered attributes.

Impact of the Number of Attributes

We then evaluate how query throughput scales as the total number of attributes 𝑚 increases from 2 to 10. In this experiment, the per-attribute range is generated uniformly from 1-100% (average 50%). Under this configuration, the expected overall query selectivity decreases exponentially with 𝑚 (i.e., 𝜎 ≈ 1/2𝑚 ). As shown in Figure 9, Garfield achieves the highest QPS at 𝑚 = 2. Throughput experiences a moderate decline (less than 2×) when scaling from 𝑚 = 2 to 𝑚 = 4, but subsequently remains almost unchanged for 𝑚 ∈ {6, 8, 10}, maintaining performance levels closely comparable to the 𝑚 = 4 baseline. This behavior validates our design choice of bounding the partition dimensionality (𝑝 = 4 by default) while still enforcing all 𝑚 attributes as strict range predicates during search. Increasing 𝑚 beyond 4 makes the predicate significantly more selective, but the marginal pruning benefits yield diminishing returns on traversal efficiency. Because cell partitioning across four attributes already localizes most candidate expansions to a highly restricted subset of cells, the remaining attributes function merely as lightweight scalar checks on a severely pruned candidate pool. This design ensures stable QPS for 𝑚 ≥ 4. Furthermore, except iRangeGraph, the majority of baseline methods fail to achieve a recall of 0.95 under these constraints. This highlights that conventional postfiltering and two-hop neighbor expansion strategies cannot supply sufficient valid candidates under multi-attribute filtering. Consequently, the naive extension of single-attribute RFANNS proves highly ineffective for multi-attribute scenarios.

6.5

Impact of the Number of Cells

To investigate the impact of the cell counts 𝑆, we construct indexes with varying 𝑆 and evaluate the performance, as illustrated in Figure 11. In Section 4.4, we argue that the setting of 𝑆 entails a trade-off, where a smaller 𝑆 results in coarse-grained filtering and a larger 𝑆 incurs severe traversal overhead across subgraphs. Our empirical results validate this analysis. Setting 𝑆 = 8 provides insufficiently granular filtering, resulting in lots of out-of-range candidates and thereby degrading performance. Conversely, while 𝑆 = 24 and 𝑆 = 36 achieve fine-grained filtering, they inflate the query complexity because a larger number of cells must be sequentially traversed. 𝑆 = 16 yields the optimal trade-off and is adopted as our configuration. 11

l=1 l=2 l=4 w/ Pipeline w/o Pipeline w Pipeline w/o Pipeline (m=2) (m=4) (m=4) 2 attribute RFANNS 2 attribute 1 attribute(m=2) RFANNS 1 attribute RFANNS on dedicated index on four-attr on dedicated index on four-attribute index on four-attribute Garfield on dedicated indexCAGRA-Post w/ Ordering Navix w/ Ordering w/index Ordering iRangeGraph GarfieldGarfield ACORN UNIFY Garfield ACORN Na (m=2) (m=1) (m=4) 2 attribute RFANNS 1 attribute RFANNS 1 attribute RFANNS w/o Ordering w/o Ordering w/o Ordering on four-attribute index on four-attribute index on dedicated index (m=2) (m=4) (m=1)

S = 36

S = 24

1 0 6

1 0 6

1 0 6

1 0

5

1 0

5

1 0

5

1 0

4

1 0

4

1 0

4

0 .8 0 .9 R e c a ll@ 1 0

1 .0

0 .7

S =SIFT1M, 8 S 1= 16 (a) 𝑚=

0 .8 0 .9 R e c a ll@ 1 0

1 .0

w/o Inter-edge (m=1)

0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 .0

0 .8 0 .9 R e c a ll@ 1 0

1 .0

1 0 3 0 .7

Q P S

(d) DBLP, 𝑚 = 1

0 .8 0 .9 R e c a ll@ 1 0

1 .0

1 0 3 0 .7

(e) DBLP, 𝑚 = 2

0 .8 0 .9 R e c a ll@ 1 0

1 0 6

1 0 6

1 0 5

1 0 5

1 0 5

1 0 4 0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 .0

1 0 4 0 .7

(a) SIFT1M, 𝑚 = 1

Q P S

l=8

1 0 6

0 .8 0 .9 R e c a ll@ 1 0

1 .0

1 0 4 0 .7

(b) SIFT1M, 𝑚 = 2 1 0 6

1 0 5

1 0 5

1 0 5

1 0 4

1 0 4 0 .7

0 .8 0 .9 R e c a ll@ 1 0

(d) DBLP, 𝑚 = 1

1 .0

1 0 4 0 .7

0 .8 0 .9 R e c a ll@ 1 0

(e) DBLP, 𝑚 = 2

1 .0

1 0 3 0 .7

0 .8 0 .9 R e c a ll@ 1 0

1 .0

2 attribute RFANNS on dedicated index

(m=1)

(m=1)

w/o Pipeline (m=1)

w/ Pipeline (m=2)

w/o Pipeline (m=2)

3 w/o 1 Ordering (m=1) 1 0 w/ Ordering (m=1) 7

w/o Ordering (m=2) w/ Ordering (m=2)

w/o Ordering (m=4) w/ Ordering (m=4)

1 3

w/o Inter-edge (m=2) 0 .9 w/ Inter-edge R e (m=2) c a ll@ 1 0

w/o Inter-edge (m=4) 1 .0 w/ Inter-edge (m=4)

4

4

(m=4)

(m=4)

w Pipeline (m=4)

w/o Pipeline (m=4)

0 .9 R e c a ll@ 1 0

1 .0

1 0

1

7

0 .8

(b) SIFT100M

Figure 14: Ablation of out-of-core pipeline. Table 3: Search latency with and without scheduling (ms). Deep100M

𝑚 Recall 0 .8 0 .9 R e c a ll@ 1 0

1 .0

SIFT100M

w/o Schedule w/ Schedule w/o Schedule w/ Schedule

(f) DBLP, 𝑚 = 4

Impact of the Number of Inter-cell Edges

Inter-cell edges constitute a major component of the index footprint. To demonstrate that a minimal number of inter-cell edges (𝑙) is sufficient to ensure efficient query, we evaluate the throughput across varying settings of 𝑙. As shown in Figure 12, with a single inter-cell edge per node (𝑙 = 1), the QPS is always lower than denser settings. However, once 𝑙 is increased to 2, it exhibits comparable performance to settings with larger 𝑙. This demonstrates that assigning merely two inter-cell neighbors per node is sufficient to propagate high-quality entry points within our search-jump-search traversal paradigm. Although more inter-cell edges may marginally improve performance, they can result in additional storage overhead. Consequently, we set 𝑙 to 2 as the default configuration.

6.7

l=8

R e c a ll@ 1 0 2 attribute RFANNS on four-attribute index

(a) Deep100M

1

0.95 0.99

0.067 0.199

0.058 0.147

0.123 0.546

0.104 0.341

2

0.95 0.99

0.071 0.362

0.059 0.201

0.162 0.687

0.133 0.348

4

0.95 0.99

0.186 0.686

0.148 0.591

0.358 1.354

0.277 0.917

Figure 12: Impact of the number of inter-cell edges.

6.6

1 .0

w/ Pipeline (m=1)

w/o Inter-edge (m=1) 1 0 .8 w/ Inter-edge (m=1)

(c) SIFT1M, 𝑚 = 4

1 0 6

0 .9

w/ Inter-edge (m=4) w/o Inter-edge 1 .0 (m=4)

l=4

Pipeline w/ Pipelineand w/ Pipeline w/ocell Pipeline w/ Pipeline w/o Pipelineof w/o Figure 13: Ablation inter-cell edges ordering. (m=2) (m=2)

1 .0

(f) DBLP, 𝑚 = 4

l=4

0 .8

w/ Inter-edge w/ Inter-edge (m=2) (m=1) 1 0 4 w/o w/o0 . Inter-edge 7 0 . 8 Inter-edge 0 .9 (m=2) (m=1)

(a) Performance comparison with (b) Performance comparison with and without inter-cell edges. and without cell ordering.

Q P S (× 1 0 3)

Q P S

l=2

0 .7

w/o Inter-edge (m=4) w/ Inter-edge (m=4)

l=2

R e c a l l @1 attribute 1 0 1 attribute RFANNS RFANNS on four-attribute index on dedicated index

4

Figure 11: Impact of the number of cells. l=1

l=1

1 0 4

w/o Inter-edge (m=2) w/ Inter-edge (m=2)

w/o Inter-edge (m=1) w/ Inter-edge 1 0 5 (m=1)

(3) Out-of-core pipeline. Figure 14 demonstrates the efficiency of the CPU-GPU pipeline detailed in Section 5.1. By overlapping data transfers with GPU computation, this pipeline yields an average performance improvement of 51.4% at a target recall of 0.9. (4) Cell-oriented scheduling. Table 3 reports the search latency with and without batch scheduling (Section 5.2). By intelligently grouping active queries, Garfield improves average search efficiency by 38.9% while incurring negligible scheduling costs.

7

Ablation Studies

Conclusion

In this paper, we presented Garfield, a novel GPU-accelerated framework for multi-attribute RFANNS. Garfield addresses the inefficiencies of existing RFANNS methods by co-designing a lightweight grid-based multi-graph (GMG) index with hardware-aware query execution engine. It enables assembly-free traversal across filtered cells while maintaining a linear and predictable index overhead. To scale beyond GPU memory, Garfield further introduces an out-ofcore pipeline that streams partial indexes under HBM constraints, schedules cell batches to minimize active queries, and overlaps transfers with GPU computation and CPU reranking. Extensive experiments on six datasets demonstrate that Garfield achieves significantly higher throughput than state-of-the-art RFANNS baselines, while maintaining low index storage overhead.

In this subsection, we demonstrate the effectiveness of the core components in Garfield through comprehensive ablation studies. (1) Inter-cell edges. Figure 13(a) depicts the performance with and without inter-cell edges. Without inter-cell edges, query performance sharply degrades. This indicates the critical role of inter-cell edges in facilitating graph traversal across disjoint cells. (2) Cell ordering. Figure 13(b) illustrates the effectiveness of cell ordering proposed in Section 4.2, which delivers an average speedup of 47.2%. As the number of filtered attributes (𝑚) increases, the performance gain slightly diminishes. This occurs because more filtered attributes result in lower selectivity, leaving fewer candidate cells to be ordered and traversed. 12

w/ Pipeline (m=2)

w/o Pip (m=4

w/ Pipeline w/o Pipeline w Pipelin (m=2) UNIFY (m=2) (m=4) CAGRA-Post

Ordering w/ Ordering w/ Ordering w/ Inter-edge iRangeGraph CAGRA-Post UNIFY w/ (m=2) (m=4) (m=1) (m=4) w/o Inter-edge w/o Ordering w/o Ordering w/o Ordering (m=4) (m=2) (m=4) (m=1)

CAGRA-Post

4

1 0

S = 16

w/o Pipeline (m=2)

w/o Pipeline (m=1) w/o Pipeline S =(m=1) 36

1 0 6

1 0 3 0 .6

1 0

1 0 4 0 .7

w/ Pipeline (m=1) w/ Pipeline S =(m=1) 24

1 0 5

1 0 5 1 0

w/o Inter-edge (m=2)

w/o Inter-edge (m=4) w/ Inter-edge (m=4)

6

1 0

1 0 5

5

S=8

w/ Inter-edge w/ Inter-edge CAGRA-Post UNIFY ACORN Navix (m=2) (m=1)

S = 24 𝑚 = 2 S = 36(c) SIFT1M, 𝑚 = 4 UNIFY (b) SIFT1M, 1 0 6

1 0 6

w/o Inter-edge (m=2) w/ Inter-edge (m=2)

Q P S

0 .7

Garfield

w/o Inter-edge (m=1) w/ Inter-edge (m=1)

Q P S (× 1 0 3)

S = 16

w/o Pipeline (m=1)

Q P S

Q P S

S=8

w/ Pipeline (m=1)

References

[27] Xiaoxi Li, Jiajie Jin, Yujia Zhou, Yuyao Zhang, Peitian Zhang, Yutao Zhu, and Zhicheng Dou. 2025. From matching to generation: A survey on generative information retrieval. TOIS 43, 3 (2025), 1–62. [28] Zhonggen Li, Xiangyu Ke, Yifan Zhu, Bocheng Yu, Baihua Zheng, and Yunjun Gao. 2025. Scalable graph indexing using GPUs for approximate nearest neighbor search. In SIGMOD. 360:1–360:27. [29] Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. Unify: Unified index for range filtered approximate nearest neighbors search. PVLDB 18, 4 (2024), 1118–1130. [30] Qiyu Liu, Yanlin Qi, Siyuan Han, Jingshu Peng, Jin Li, and Lei Chen. 2025. Not small enough? SegPQ: A learned approach to compress product quantization codebooks. PVLDB 18, 11 (2025), 3730–3743. [31] Duo Lu, Helena Caminal, Manos Chatzakis, Yannis Papakonstantinou, Yannis Chronis, Vaibhav Jain, and Fatma Özcan. 2026. An in-depth study of filteragnostic vector search on a postgresql database system. arXiv (2026). [32] Ruiyao Ma, Yifan Zhu, Baihua Zheng, Lu Chen, Congcong Ge, and Yunjun Gao. 2024. GTI: Graph-based tree index with logarithm updates for nearest neighbor search in high-dimensional spaces. PVLDB 18, 4 (2024), 986–999. [33] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. TPAMI 42, 4 (2018), 824–836. [34] Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. Parlayann: Scalable and deterministic parallel graph-based approximate nearest neighbor search algorithms. In PPoPP. 270–285. [35] Xupeng Miao, Yining Shi, Hailin Zhang, Xin Zhang, Xiaonan Nie, Zhi Yang, and Bin Cui. 2022. HET-GMP: A graph-based system approach to scaling large embedding model training. In SIGMOD. 470–480. [36] Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. 2024. Cagra: Highly parallel graph construction and approximate nearest neighbor search for gpus. In ICDE. 4236–4247. [37] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems. VLDBJ 33, 5 (2024), 1591–1615. [38] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. Acorn: Performant and predicate-agnostic search over vector embeddings and structured data. In SIGMOD. 120:1–120:27. [39] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient approximate nearest neighbor search in multi-dimensional databases. In SIGMOD. 54:1–54:27. [40] Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2025. Dynamic range-filtering approximate nearest neighbor search. PVLDB 18, 10 (2025), 3256–3268. [41] Runwen Qiu and Jing Tang. 2025. Efficient approximate nearest neighbor search via hemi-sphere centroids graph. In SIGMOD. 321:1–321:26. [42] Gaurav Sehgal and Semih Salihoglu. 2025. NaviX: A native vector index design for graph dbmss with robust predicate-agnostic search performance. PVLDB 18, 11 (2025), 4438–4450. [43] Bing Tian, Haikun Liu, Yuhang Tang, Shihai Xiao, Zhuohui Duan, Xiaofei Liao, Hai Jin, Xuecang Zhang, Junhua Zhu, and Yu Zhang. 2025. Towards highthroughput and low-latency billion-scale vector search via CPU/GPU collaborative filtering and re-ranking. In FAST. 171–185. [44] 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 SIGMOD. 2614–2627. [45] 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. NeurIPS 36 (2023), 15738–15751. [46] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. PVLDB 14, 11 (2021), 1964–1978. [47] Ziqi Wang, Jingzhe Zhang, and Wei Hu. 2025. WoW: A window-to-window incremental index for range-filtering approximate nearest neighbor search. In SIGMOD. 378:1–378:27. [48] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A hybrid analytical engine towards query fusion for structured and unstructured data. PVLDB 13, 12 (2020), 3152–3165. [49] Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng. 2025. Subspace collision: An efficient and accurate framework for high-dimensional approximate nearest neighbor search. In SIGMOD. 79:1–79:29. [50] Wei Wu, Junlin He, Yu Qiao, Guoheng Fu, Li Liu, and Jin Yu. 2022. HQANN: Efficient and robust similarity search for hybrid queries with structured and unstructured constraints. In CIKM. 4580–4584. [51] Jingyi Xi, Chenghao Mo, Ben Karsin, Artem Chirkin, Mingqin Li, and Minjia Zhang. 2025. VecFlow: A high-performance vector data management system for filtered-search on GPUs. In SIGMOD. 271:1–271:27. [52] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S Jensen. 2024. iRangeGraph: Improvising range-dedicated graphs for range-filtering nearest neighbor search. In SIGMOD. 239:1–239:26.

[1] [2] [3] [4]

2010. SIFT. http://corpus-texmex.irisa.fr. 2019. YouTube. https://research.google.com/youtube8m/download.html. 2025. DBLP. https://open.aminer.cn/open/article?id=655db2202ab17a072284bc0c. 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. In SIGMOD. 212:1–212:26. [5] Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-based vector search: An experimental evaluation of the state-of-the-art. In SIGMOD. 43:1– 43:31. [6] Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. In CVPR. 2055–2063. [7] Yuzheng Cai, Jiayang Shi, Yizhuo Chen, and Weiguo Zheng. 2024. Navigating labels and vectors: A unified approach to filtered approximate nearest neighbor search. In SIGMOD. 246:1–246:27. [8] Cheng Chen, Chenzhe Jin, Yunan Zhang, Sasha Podolsky, Chun Wu, SzuPo Wang, Eric Hanson, Zhou Sun, Robert Walzer, and Jianguo Wang. 2024. Singlestore-v: An integrated vector database system in singlestore. PVLDB 17, 12 (2024), 3772–3785. [9] Jatin Chhugani, Anthony D Nguyen, Victor W Lee, William Macy, Mostafa Hagog, Yen-Kuang Chen, Akram Baransi, Sanjeev Kumar, and Pradeep Dubey. 2008. Efficient implementation of sorting on multi-core SIMD CPU architecture. PVLDB 1, 2 (2008), 1313–1324. [10] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. PVLDB 12, 5 (2019), 461–474. [11] 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 WWW. 3406–3416. [12] Zengyang Gong, Yuxiang Zeng, and Lei Chen. 2025. Accelerating approximate nearest neighbor search in hierarchical graphs: Efficient level navigation with shortcuts. PVLDB 18, 10 (2025), 3518–3530. [13] Yutong Gou, Jianyang Gao, Yuexuan Xu, and Cheng Long. 2025. SymphonyQG: Towards symphonious integration of quantization and graph for approximate nearest neighbor search. In SIGMOD. 80:1–80:26. [14] Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, et al. 2022. Cardinality estimation in DBMS: A comprehensive benchmark evaluation. PVLDB 15, 4 (2022), 752–765. [15] Guoyu Hu, Shaofeng Cai, Tien Tuan Anh Dinh, Zhongle Xie, Cong Yue, Gang Chen, and Beng Chin Ooi. 2025. HAKES: Scalable vector database for embedding search service. PVLDB 18, 9 (2025), 3049–3062. [16] Haodi Jiang, Hao Guo, Minhui Xie, Jiwu Shu, and Youyou Lu. 2025. Highthroughput, cost-effective billion-scale vector search with a single GPU. In SIGMOD. 334:1–334:27. [17] 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. In SIGMOD. 148:1–148:26. [18] Wenqi Jiang, Zhenhao He, Shuai Zhang, Kai Zeng, Liang Feng, Jiansong Zhang, Tongxuan Liu, Yong Li, Jingren Zhou, Ce Zhang, et al. 2021. Fleetrec: Large-scale recommendation inference on hybrid gpu-fpga clusters. In SIGKDD. 3097–3105. [19] Wenqi Jiang, Marco Zeller, Roger Waleffe, Torsten Hoefler, and Gustavo Alonso. 2024. Chameleon: A heterogeneous and disaggregated accelerator system for retrieval-augmented language models. PVLDB 18, 1 (2024), 42–52. [20] Yicheng Jin, Yongji Wu, Wenjun Hu, Bruce Maggs, Jun Yang, Xiao Zhang, and Danyang Zhuo. 2026. Curator: Efficient vector search with low-selectivity filters. In SIGMOD. 21:1–21:27. [21] V Karthik, Saim Khan, Somesh Singh, Harsha Vardhan Simhadri, and Jyothi Vedurada. 2025. BANG: Billion-scale approximate nearest neighbour search using a single GPU. IEEE Transactions on Big Data 11, 6 (2025), 3142–3157. [22] Kyoungmin Kim, Sangoh Lee, Injung Kim, and Wook-Shin Han. 2024. Asm: Harmonizing autoregressive model, sampling, and multi-dimensional statistics merging for cardinality estimation. In SIGMOD. 45:1–45:27. [23] Sukjin Kim, Seongyeon Park, Si Ung Noh, Junguk Hong, Taehee Kwon, Hunseong Lim, and Jinho Lee. 2025. PathWeaver: A high-throughput multi-GPU system for graph-based approximate nearest neighbor search. In USENIX ATC. 1501–1517. [24] Hai Lan, Shixun Huang, Zhifeng Bao, and Renata Borovica-Gajic. 2024. Cardinality estimation for similarity search on high-dimensional data objects: The impact of reference objects. PVLDB 18, 3 (2024), 544–556. [25] Mocheng Li, Xiao Yan, Baotong Lu, Yue Zhang, James Cheng, and Chenhao Ma. 2025. Attribute filtering in approximate nearest neighbor search: An in-depth experimental study. In SIGMOD. 298:1–298:26. [26] Peizheng Li, Chaoyi Chen, Hao Yuan, Zhenbo Fu, Hang Shen, Xinbo Yang, Qiange Wang, Xin Ai, Yanfeng Zhang, Yingyou Wen, et al. 2025. Neutronrag: Towards understanding the effectiveness of RAG from a data retrieval perspective. In SIGMOD Companion. 163–166.

13

[60] Huayi Zhang, Lei Cao, Yizhou Yan, Samuel Madden, and Elke A Rundensteiner. 2020. Continuously adaptive similarity search. In SIGMOD. 2601–2616. [61] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, et al. 2023. Vbase: Unifying online vector similarity search and relational queries via relaxed monotonicity. In OSDI. 377–395. [62] Weijie Zhao, Shulong Tan, and Ping Li. 2020. Song: Approximate nearest neighbor search on gpu. In ICDE. 1033–1044. [63] Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards efficient index construction and approximate nearest neighbor search in highdimensional spaces. PVLDB 16, 8 (2023), 1979–1991. [64] Yingli Zhou, Yaodong Su, Youran Sun, Shu Wang, Taotao Wang, Runyuan He, Yongwei Zhang, Sicong Liang, Xilin Liu, Yuchi Ma, et al. 2025. In-depth analysis of graph-based RAG in a unified framework. PVLDB 18, 13 (2025), 5623–5637. [65] Jiaxu Zhu, Jiayu Yuan, Kaiwen Yang, Xiaobao Chen, Shihuan Yu, Hongchang Lv, Yan Li, and Bolong Zheng. 2025. An experimental evaluation of hybrid querying on vectors. PVLDB 19, 2 (2025), 183–195. [66] Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. Serf: Segment graph for range-filtering approximate nearest neighbor search. In SIGMOD. 69:1–69:26.

[53] Chen Yang, Sunhao Dai, Yupeng Hou, Wayne Xin Zhao, Jun Xu, Yang Song, and Hengshu Zhu. 2024. Revisiting reciprocal recommender systems: Metrics, formulation, and method. In SIGKDD. 3714–3723. [54] Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. Pase: Postgresql ultra-highdimensional approximate nearest neighbor search extension. In SIGMOD. 2241– 2253. [55] Chunxiao Ye, Xiao Yan, and Eric Lo. 2025. Compass: General filtered search across vector and structured data. arXiv (2025). [56] 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 (2026). [57] Yuanhang Yu, Dong Wen, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2022. GPU-accelerated proximity graph approximate nearest neighbor search and construction. In ICDE. 552–564. [58] Yuxiang Zeng, Yongxin Tong, and Lei Chen. 2023. Litehst: A tree embedding based method for similarity search. In SIGMOD. 35:1–35:26. [59] 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. In SIGMOD. 152:1–152:26.

14

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181