Simple and Fast Algorithm for Graph-based Filtered Approximate Nearest Neighbor Search (Full Version)

HEXA: A Disjoint-Subgraph-Based Indexing Framework for Approximate Nearest Neighbor Search at Billion Scale

Approximate Nearest Neighbor (ANN) search is a core operation in large-scale vector databases that support recommendation, semantic search, and retrieval-augmented generation. Graph-based indexes are widely used for their superior search performance at million scale, but scaling them to billion-scale datasets exposes a fundamental trade-off between construction efficiency and search performance. CPU-based methods produce high-quality graphs enabling fast search but require multiple days to construct, while GPU-based methods accelerate construction at the cost of degraded search performance. This trade-off stems from the traditional requirement of enforcing global connectivity during graph construction. We observe that graph-based search primarily depends on local connectivity between entry points and a query's nearest neighbors, making global connectivity unnecessary for high search performance. In this paper, we introduce HEXA, a disjoint-subgraph-based indexing framework that partitions the dataset into disjoint clusters and constructs refined proximity subgraphs independently on GPUs. At query time, HEXA employs a two-level routing structure to select relevant subgraphs and query-close entry points, then applies a budget-adaptive search algorithm that allocates exploration effort based on each subgraph's likelihood of containing nearest neighbors. Experiments on billion-scale datasets demonstrate that HEXA achieves up to 14.7 times higher query throughput at the same recall levels compared with various indexing methods, and reduces construction time to approximately one hour.

FROG: Efficient Range-Filtering Approximate Nearest Neighbor Search on GPUs

FROG is a GPU-oriented RFANNS index that replaces multiple locally optimal substructure building with a globally aware, vertex-centric design and organizes diverse expansion neighbor candidates for each vertex in a GPU-friendly structure and rapidly identifies the expansion neighbors used for computation at query time.

Pail: Efficient 𝑘 NN Search on Set-Valued Attributes

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

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

Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification

Approximate nearest neighbor search (ANNS) retrieves the most similar vectors to a query vector in high-dimensional space. Label-filtering ANNS (LFANNS) extends ANNS with a label filter that the labels of base vectors must satisfy a set relation (e.g., equality, containment, or overlap) with the query labels. Existing LFANNS indices suffer from inconsistent performance across different filter types and degraded scalability under varying label scale and distribution. In this paper, we define label-stratified similarity graph (LSSG), where edges connect neighboring vectors whose label sets fall within stratified similarity thresholds. To implement LSSG efficiently, we design an incremental insertion algorithm to prune redundant edges in both vector and label spaces, and leverage a MinHash structure to ensure scalability for large-scale labels. We analyze stepwise probabilities under explicit label models and explain why stricter label tiers reduce ineffective in-filtering expansions. Benchmark experiments show that LSSG achieves ideal optimality for equality queries, and 1.06x-92.9x and 1.08x-84.1x faster than the best competing index for containment and overlap, respectively, in query speed with identical accuracy and 0.35x index size.

Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search

Range-filtered approximate nearest neighbor search (RFANNS) is an important primitive for vector databases; it retrieves vectors that are similar to a query and satisfy a numerical range predicate, but existing RFANNS indexes expose vectors, attributes, and queries in plaintext. This assumption is unsuitable for outsourced vector databases, where sensitive data and queries must be protected from an honest-but-curious cloud server. To the best of our knowledge, this is the first study that systematically formulates and evaluates privacy-preserving RFANNS over outsourced encrypted vector databases. Our approach separates range localization from encrypted vector search: an authorized user maps the query range to a compact set of nodes in a local N-ary attribute tree, and the server searches only the corresponding proximity graph sub-indices over encrypted vectors. To reduce expensive encrypted comparisons, we use a filter-and-refine pipeline that first retrieves coarse candidates with approximate distance-comparison-preserving encryption and then reranks a small candidate set with exact distance-comparison encryption. We then analyze the computation, storage, communication, and leakage of the protocol. Experiments on four widely used vector datasets show that our method improves the QPS-Recall trade-off over representative secure adaptations of existing RFANNS approaches, scaling effectively to large datasets.