Source-linked AI summary
Grant: A Framework for Approximate Nearest Neighbor Search with Multi-Attribute Range Filters
Daichi Amagata
TL;DR
Multi-attribute range-filter ANNS lacks a solution that combines efficiency and generality, and some methods depend on past query workloads. Grant combines an attribute-value tree with graph-based ANNS in its leaf nodes. Across four datasets, Grant generally achieves better time-recall tradeoffs than existing state-of-the-art methods.
Problem
No existing work combines efficiency and generality for multi-attribute range-filter ANNS, and some methods require past query workloads.
Source: §1.2 · p. 2, §1.1 · p. 2Method
Grant uses a tree over attribute values for range search and builds graph-based ANNS indices in the tree's leaf nodes.
Source: §4 · p. 4, §4.1 · p. 5Results
0.9 high-recall results were obtained within a few milliseconds; Grant algorithms generally had better time-recall tradeoffs than existing state-of-the-art methods on four datasets.
Source: §5.2 · p. 10, §6 · p. 11Takeaways & Limitations
Grant addresses a more general problem than single-attribute or matching-filter ANNS, where the paper reports no existing work satisfying efficiency and generality together.
Source: §1.2 · p. 2Some prior methods for multi-attribute range filters [34] [29] require past queries and do not function without them.
Source: §1.1 · p. 2
Abstract
from arXiv · showhide
Recently, academia and industry have considered the problem of approximate nearest neighbor search (ANNS) with filters. In this setting, each object consists of a high-dimensional vector and attribute values. Given a query vector, filters for attribute values, and $k$, this problem retrieves $k$ vectors approximately nearest to the query vector among a set of objects passing the filters. This paper considers range filters, i.e., users can specify a range constraint for each attribute. Most existing works do not consider this setting, and they assume (i) only a single attribute or (ii) matching filters that require the same attribute values or categories. Existing techniques for these assumptions are not available for our setting or are trivially not efficient. Although standard solutions, such as pre-filter and post-filter, can handle our problem, they are also inefficient. Some works tackle the same problem as ours, but their techniques necessitate historical query workloads, which significantly limit practical use cases. To remove these limitations, this work proposes Grant, a novel framework that solves this problem efficiently while accepting arbitrary range filters and ANNS data structures. Grant can guarantee a search time sub-linear to the number of objects, which is not held by existing techniques. We conduct extensive experiments, and their results demonstrate that Grant outperforms existing techniques.
1 Introduction
ANNS with attribute filters supports applications such as e-commerce and RAG, but existing approaches do not jointly provide efficient, general support for multi-attribute range filters. Grant combines graph indices with a tree index to address this gap.
1 Introduction
- ANNS with attribute filters matters in e-commerce and RAG, where queries can constrain product attributes or age and blood pressure.High-dimensional exact nearest-neighbor search is computationally expensive, motivating approximate search.Source: §1 · p. 1
1.1 Limitations of Prior Work
- Prior approaches assume one attribute, support only matching filters, require past queries, or rely on inefficient pre-filter or post-filter methods.Matching-filter techniques are inefficient for multiple range filters because they require iterations across continuous ranges.Source: §1.1 · pp. 1–2
1.2 Contribution
- Grant incorporates graph indices into a tree index to handle multiple attributes and arbitrary ranges, operating without past query workloads while allowing past vectors to accelerate search.The framework can employ state-of-the-art multidimensional tree indices and proximity graphs.Source: §1.2 · p. 2
- With a kd-tree base, Grant guarantees sub-linear ANNS time, and experiments report that it outperforms state-of-the-art baselines in most tests.The paper presents this theoretical guarantee as not achieved by existing algorithms for multi-attribute range-filtered ANNS.Source: §1.2 · p. 2
2 Preliminary
Section 2 defines approximate nearest-neighbor search over objects with vectors and multiple attributes, then reviews graph-index search and baseline filtering approaches.
2.1 Problem Definition
- Approximate search returns k objects satisfying every range filter, aiming to match the exact nearest objects; when fewer than k objects qualify, all qualifying objects are returned.The analysis assumes an in-memory setting and d = O(1), since the algorithms scale linearly with d.Source: §2.1 · pp. 2–3
2.2 Graph Index for ANNS
- Graph-index search greedily traverses from an entry vertex, visiting unvisited neighbors and prioritizing those nearest to the query until no closer vectors are found.Graph edges can follow relative-neighbor structure, which excludes an edge when another vector is closer to its endpoint.Source: §2.2 · p. 3
2.3 Baseline Algorithms
- Pre-filter scans the objects passing the query filters and can return exact results, but its query-dependent candidate set prevents use of an ANNS index.A brute-force scan instead checks all objects and computes distances only for those satisfying the filters, requiring O(n) distance computations.Source: §2.3 · p. 3
- Post-filter searches a pre-built ANNS index, enlarging k and repeating the search until k results pass the filters; ignoring attributes can require many iterations.Its search space can therefore be large.Source: §2.3 · p. 3
- ACORN traverses only filter-passing neighbors, but may lose paths toward the query when none of a vertex’s neighbors pass the filter, lowering recall.The passage says experiments confirm this observation.Source: §2.3 · p. 3
3 Related Work
Related work covers graph indices for filtered search, range-filter structures, workload-dependent methods, and vector data systems. The cited approaches have limits in filter scope, workload assumptions, or query processing.
Graph indices
- Grant can use an arbitrary graph index to maintain the high-dimensional vectors in the dataset.Graph indices are described as offering a strong time-recall trade-off for ANNS.Source: §3 · p. 3
ANNS with Matching Filter
- Matching-filter methods use edge labels, per-label graphs, or combined vector-and-label similarity, but do not support multi-attribute cases and/or range filters [51] [37] [42].FilteredVamana labels edges, StitchedVamana builds a graph for each label, and NHQ uses a customized distance function.Source: §3 · p. 4
ANNS with Range Filter
Multi-attribute range filters
Vector Data Management Systems
4 Grant
Grant combines attribute-based range indexing with graph-based ANNS to seek objects that satisfy range filters and resemble the query. Its basic design is workload-free, with past-query information available as an optional accelerator.
4 Grant
- Grant combines attribute trees and vector graphs to run graph-based ANNS on range-query results, avoiding the limitations of pre-filter and post-filter.Source: §4 · p. 4
4.1 Grant Structure
- Attribute-based tree leaves hold up to O(n/c) objects and graph indices, enabling simultaneous attribute- and vector-based navigation.Grant uses O(1)+S(n) space, and its construction takes O(n(1+f(n))) + g(n) time.Source: §4.1 · pp. 4–5
4.2 ANNS on Grant
- At query time, Grant finds leaves overlapping F, searches their graph indices, and filters returned objects; with a kd-tree, runtime is O(n^(1-1/m)).Source: §4.2 · pp. 5–6
4.3 Optimizing ANNS on Grant by Heuristic
- When |U| exceeds O(k), Grant estimates each leaf's valid candidates under local-uniform attributes and probabilistically prioritizes graph searches.Source: §4.3 · p. 6
4.4 Workload-aware ANNS
- When past query vectors are available, an optional index and distance matrix select O(k) overlapping leaves nearest to a similar past query.The workload-aware option requires additional preprocessing and can be applied on top of the original query processing.Source: §4.4 · p. 7
5 Experiment
The experiments compare Grant with existing methods on four large datasets and report generally better time–recall tradeoffs. They also examine resource use, parameter sensitivity, and the effects of Grant’s query-processing heuristics.
5.1 Setting
- The evaluation uses four 10-million-vector datasets with power-law attribute values; the default query setting uses two attributes, range fraction 0.2, and k = 10.The default average filter selectivity is 0.15.Source: §5.1 · p. 8
5.2 Result
- Grant is not very sensitive to c but has an optimum: large c adds overlapping-leaf ANNS searches, while small c leaves more objects that fail the filters.Figure 3 reports QPS under recall ≈0.9.Source: §5.2 · p. 9, Figure 3 · p. 9
- For 10 million vectors, Grant indexing takes at most 1.5 minutes and uses less than about 10GB; indexing is shorter than IVF, Post-filter, and ACORN.Grant and Pre-filter use less memory than Post-filter; Grant uses more memory than Pre-filter and IVF.Source: §5.2 · p. 9, Table 2 · p. 10, Table 3 · p. 10
- Grant’s algorithms generally deliver better time–recall tradeoffs than existing state-of-the-art methods across four datasets, reaching recall 0.9 within a few milliseconds.The comparison uses QPS versus recall curves.Source: §5.2 · p. 10, Figure 4 · p. 10
- Grant-pnv improves efficiency over Grant-basic by about 1.3–1.5x without recall drop, relieving the graph-based ANNS bottleneck rather than Range-Search.Table 4 reports decomposed time at recall ≈0.9.Source: §5.2 · p. 10, Table 4 · p. 10
- At recall@10 = 0.9, WA-Grant is substantially better than SIEVE and more than 2 times faster than Grant-pnv.The comparison with SIEVE uses the same memory budget; WA-Grant uses past query vectors.Source: §5.2 · pp. 10–11, Figure 5 · p. 11
6 Conclusion
The paper concludes that Grant addresses approximate nearest-neighbor search with multi-attribute range filters, and that experiments show it outperforms existing state-of-the-art techniques. It identifies static data and a small number of filtered attributes as scope boundaries.
6 Conclusion
- Grant is a new data structure for multi-attribute range-filtered ANNS, supported by theoretical efficiency analysis and two query-processing heuristics.The experiments are reported to show that Grant outperforms existing state-of-the-art techniques.Source: §6 · p. 11
- The analysis assumes static data, leaving insertions and deletions open, and Grant may be inefficient when many attributes are filtered.The paper assumes m is small because real-world datasets tend to have few attributes with specified ranges.Source: §6 · p. 11
A Additional Experiments
Across changes in k, attribute count, and range size, Grant outperforms the compared algorithms. Its QPS declines as k grows, while its performance is robust to range size.
Impact of k
- Grant-pnv remains much faster than existing algorithms as k increases, although its QPS declines and Post-filter falls below 40 QPS at k=50.BF, Pre-filter, and IVF are unaffected by k; ACORN cannot reach recall ≈0.9 when k≥20.Source: A Additional Experiments · p. 11, Figure 6 · p. 12
Impact of m
- Grant continues to outperform the other algorithms as the number of attributes m increases, while Post-filter worsens and Pre-filter improves.A larger m usually yields a smaller range-search result set; ACORN fails to reach recall ≈0.9 when m≥3.Source: A Additional Experiments · p. 11, Figure 7 · p. 12
Impact of range size
- Grant's performance is robust to range size, and Post-filter does not catch up even when the range is large.As range size grows, Pre-filter performance worsens while Post-filter performance improves.Source: A Additional Experiments · p. 11, Figure 8 · p. 12