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.
Abstract
Range-filtering approximate nearest neighbor search (RFANNS) is a fundamental operation in modern vector databases. Given a query vector $q$ and a numerical range predicate, RFANNS returns the $k$-approximate nearest neighbors ($k$-ANN) of the query $q$ among the objects whose attributes satisfy the range predicate. However, existing RFANNS methods are not well suited to high-throughput GPU execution. CPU indexes offer limited parallel scalability, generic GPU filtering is highly selectivity-dependent, and GPU indexes built from locally optimized subgraphs can incur long search trajectories and redundant distance computations. To address these limitations, we present FROG, a GPU-oriented RFANNS index that replaces multiple locally optimal substructure building with a globally aware, vertex-centric design. It 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. Moreover, GPU-oriented algorithms and implementations are developed for both index construction and query processing. Experiments on six datasets show that FROG improves mixed-selectivity query throughput by 14.7--37.7$\times$ over 44-core CPU baselines and 4.5--7.6$\times$ over the strongest GPU baseline. It also accelerates index construction by 2.4--14.8$\times$ over the GPU baseline.
GrAND (GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search) is presented, a GPU-native collection of dynamic-update algorithms for two popular graph indexes, Vamana and CAGRA, that improves overall workload throughput and maintains high search throughput and recall over sustained updates.
Karthik Venkatasubba, Shivendra Deshpande, S. Shivram et al.· 0 citations
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.
Yi-Fei Xu, Yan-Yan Shen, Youmin Chen et al.· Proceedings of the VLDB Endo...· 0 citations
This work proposes a new algorithm, called filtered approximate nearest neighbor search, that retrieves approximate nearest neighbors from a set of objects that have the specified attribute values and demonstrates the efficiency of this algorithm.
This paper addresses both $k-Nearest Neighbor Graph (kNNG) construction on 1024-dimensional BGE-M3 embeddings and Maximum Inner Product Search (MIPS) on unnormalized Llama-3.2-8B features, and introduces a 1D presorting mechanism via Fast Linear Assignment Sorting (FLAS) prior to graph construction.
Nico Hezel, Kai Barthel, Bruno Schilling et al.· arXiv.org· 0 citations
RVANNS is presented, an RVV-oriented ANNS engine that jointly optimizes vector representation and graph locality and achieves 3.39x and 4.94x speedups over scalar execution on real 128-bit and 256-bit RVV processors, respectively.
Chengying Huan, Yudong Liu, Jian-Guo Wang et al.· 0 citations
This paper proposes an adaptive framework for ANNS that explicitly incorporates user-specified recall requirements into the search process by employing an early termination strategy, and introduces two learning-based mechanisms, one for dynamically predicting the achieved recall during the search and triggers early termination once the predicted recall satisfies the target threshold.
Shuang Hao, Xinxin Li, Wei Zhang· Proceedings of the 32nd ACM...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
