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
It has been common to represent many objects as high-dimensional vectors due to the proliferation of machine learning-based embedding techniques. One of the most important functions for analyzing high-dimensional vectors is approximate nearest neighbor search, which, given a query vector, retrieves the vector that is approximately the most similar to the query vector. In many real-world applications, such as e-commerce, objects have not only vectors but also attributes, e.g., category, color, and brand, and they require a scenario where users can specify a query vector and a value for each attribute of interest. This problem, called filtered approximate nearest neighbor search, retrieves approximate nearest neighbors from a set of objects that have the specified attribute values. Efficiently solving this problem is challenging because it has to accept arbitrary query vectors and attribute values, which are not known in advance. Existing techniques suffer from slow search performance and difficulty in dealing with arbitrary combinations of attributes. This work overcomes these challenges and proposes a new algorithm for this problem. We conduct extensive experiments, and the results demonstrate the efficiency of our 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
Approximate nearest neighbor search (ANNS) is a fundamental operation in large-scale vector retrieval systems, where achieving high recall under strict latency constraints is essential. Existing ANNS approaches typically control recall using fixed search parameters, such as a predefined candidate neighbor set (CNS) size, which require significant effort to fine-tune for each use case. Even worse, due to substantial heterogeneity in query difficulty and data distribution, static parameterization often results in over-searching for easy queries and under-searching for hard ones. In this paper, we propose an adaptive framework for ANNS that explicitly incorporates user-specified recall requirements into the search process by employing an early termination strategy. We introduce 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, and another for estimating the minimal CNS size required to satisfy user needs during the search, enabling dynamic scaling of the CNS. Our framework is index-agnostic and can be seamlessly integrated into widely used graph-based ANN indexes, including HNSW, with negligible overhead. Extensive experiments on benchmark datasets and various graph indexes demonstrate that our methods significantly reduce query latency compared to state-of-the-art baselines. Our code is available at https://github.com/lxxabb/Recall-Aware-Early-Termination-in-Approximate-Nearest-Neighbor-Search.
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.
