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

• URL: http://arxiv.org/abs/2608.16491v1
• Date: Mon, 17 Aug 2026 12:29:11 GMT
• Title: FROG: Efficient Range-Filtering Approximate Nearest Neighbor Search on GPUs
• Abstract summary: Range-filtering approximate nearest neighbor search (RFANNS) is a fundamental operation in modern vector databases.<n>We present FROG, a GPU-oriented RFANNS index that replaces multiple locally optimal substructure building.<n>Experiments show 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.
• Score: 19.82431161075971
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• GraphGP: Scalable Gaussian Processes with Vecchia's Approximation [0.0]
  Vecchia's approximation is a sparse precision matrix approximation for stationary, decaying kernels.<n>We present GraphGP, an algorithm for Vecchia's approximation that scales to nearly a billion parameters with linear time and memory requirements.
  arXiv  Detail & Related papers  (2026-06-09T19:50:27Z)
• GRAB-ANNS: High-Throughput Indexing and Hybrid Search via GPU-Native Bucketing [39.763467046232584]
  We present GRAB-ANNS, a GPU-native graph index for dynamic hybrid search.<n>We show that GRAB-ANNS achieves up to 240.1 times higher query throughput and 12.6 times faster index construction than state-of-the-art CPU-based systems.
  arXiv  Detail & Related papers  (2026-03-31T11:00:10Z)
• GPU-Native Approximate Nearest Neighbor Search with IVF-RaBitQ: Fast Index Build and Search [6.459073253087106]
  IVF-RaBitQ is a GPU-native ANNS solution that integrates the cluster-based method IVF with RaBitQ quantization into an efficient GPU index build/search pipeline.<n>We show that IVF-RaBitQ offers a strong performance frontier in recall, throughput, index build time, and storage footprint.
  arXiv  Detail & Related papers  (2026-02-27T13:23:30Z)
• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions [54.570944939061555]
  We present a comprehensive study of GPU-accelerated graph-based vector search algorithms.<n>We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units.<n>Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems.
  arXiv  Detail & Related papers  (2026-02-10T16:18:04Z)
• NGPU-LM: GPU-Accelerated N-Gram Language Model for Context-Biasing in Greedy ASR Decoding [54.88765757043535]
  This work rethinks data structures for statistical n-gram language models to enable fast and parallel operations for GPU-optimized inference.<n>Our approach, named NGPU-LM, introduces customizable greedy decoding for all major ASR model types with less than 7% computational overhead.<n>The proposed approach can eliminate more than 50% of the accuracy gap between greedy and beam search for out-of-domain scenarios while avoiding significant slowdown caused by beam search.
  arXiv  Detail & Related papers  (2025-05-28T20:43:10Z)
• iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search [24.85572470526277]
  Range-filtering approximate nearest neighbor (RFANN) search is attracting increasing attention in academia and industry. Recent study proposes to build $O(n2)$ dedicated graph-based indexes for all possible query ranges. We materialize graph-based indexes, called elemental graphs, for a moderate number of ranges.
  arXiv  Detail & Related papers  (2024-09-04T09:41:52Z)
• INR-Arch: A Dataflow Architecture and Compiler for Arbitrary-Order Gradient Computations in Implicit Neural Representation Processing [66.00729477511219]
  Given a function represented as a computation graph, traditional architectures face challenges in efficiently computing its nth-order gradient. We introduce INR-Arch, a framework that transforms the computation graph of an nth-order gradient into a hardware-optimized dataflow architecture. We present results that demonstrate 1.8-4.8x and 1.5-3.6x speedup compared to CPU and GPU baselines respectively.
  arXiv  Detail & Related papers  (2023-08-11T04:24:39Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• Towards Improving the Consistency, Efficiency, and Flexibility of Differentiable Neural Architecture Search [84.4140192638394]
  Most differentiable neural architecture search methods construct a super-net for search and derive a target-net as its sub-graph for evaluation. In this paper, we introduce EnTranNAS that is composed of Engine-cells and Transit-cells. Our method also spares much memory and computation cost, which speeds up the search process.
  arXiv  Detail & Related papers  (2021-01-27T12:16:47Z)
• Hybrid Models for Learning to Branch [81.93868699246214]
  We propose a new hybrid architecture for efficient branching on CPU machines. The proposed architecture combines the expressive power of GNNs with computationally inexpensive multi-layer perceptrons (MLP) for branching.
  arXiv  Detail & Related papers  (2020-06-26T21:03:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.