GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions

• URL: http://arxiv.org/abs/2602.16719v1
• Date: Tue, 10 Feb 2026 16:18:04 GMT
• Title: GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions
• Authors: Yaowen Liu, Xuejia Chen, Anxin Tian, Haoyang Li, Qinbin Li, Xin Zhang, Alexander Zhou, Chen Jason Zhang, Qing Li, Lei Chen,
• Abstract summary: 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.
• Score: 54.570944939061555
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Approximate Nearest Neighbor Search (ANNS) underpins many large-scale data mining and machine learning applications, with efficient retrieval increasingly hinging on GPU acceleration as dataset sizes grow. Although graph-based approaches represent the state of the art in approximate nearest neighbor search, there is a lack of systematic understanding regarding their optimization for modern GPU architectures and their end-to-end effectiveness in practical scenarios. In this work, we present a comprehensive survey and experimental study of GPU-accelerated graph-based vector search algorithms. We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units within GPUs. Through a thorough evaluation of six leading algorithms on eight large-scale benchmark datasets, we assess both graph index construction and query search performance. Our analysis reveals that distance computation remains the primary computational bottleneck, while data transfer between the host CPU and GPU emerges as the dominant factor influencing real-world latency at large scale. We also highlight key trade-offs in scalability and memory usage across different system designs. Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems, and provide a comprehensive benchmark for the knowledge discovery and data mining community.

Related papers

• On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU [14.338954144116759]
  Graph-based Approximate Nearest Neighbor Search (ANNS) has become the dominant paradigm for modern AI applications.<n>We present the first systematic investigation of graph reordering effects for graph-based ANNS on a GPU.
  arXiv  Detail & Related papers  (2025-08-21T10:50:49Z)
• Enabling High Data Throughput Reinforcement Learning on GPUs: A Domain Agnostic Framework for Data-Driven Scientific Research [90.91438597133211]
  We introduce WarpSci, a framework designed to overcome crucial system bottlenecks in the application of reinforcement learning. We eliminate the need for data transfer between the CPU and GPU, enabling the concurrent execution of thousands of simulations.
  arXiv  Detail & Related papers  (2024-08-01T21:38:09Z)
• Implementation and Analysis of GPU Algorithms for Vecchia Approximation [0.8057006406834466]
  Vecchia Approximation is widely used to reduce the computational complexity and can be calculated with embarrassingly parallel algorithms. While multi-core software has been developed for Vecchia Approximation, software designed to run on graphics processing units ( GPU) is lacking. We show that our new method outperforms the other two and then present it in the GpGpU R package.
  arXiv  Detail & Related papers  (2024-07-03T01:24:44Z)
• GPU Based Differential Evolution: New Insights and Comparative Study [7.5961910202572644]
  This work reviews the main architectural choices made in the literature for GPU based Differential Evolution algorithms. It introduces a new GPU based numerical optimisation benchmark to evaluate and compare GPU based DE algorithms.
  arXiv  Detail & Related papers  (2024-05-26T12:40:39Z)
• CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs [4.55224304015001]
  We introduce a novel parallel computing hardware-based proximity graph and search algorithm. By leveraging the high-performance capabilities of modern hardware, our approach achieves remarkable efficiency gains. In large-batch query throughput in the 90% to 95% recall range, our method is 3377x faster than HNSW, and is 3.88.8x faster than the SOTA implementations for GPU.
  arXiv  Detail & Related papers  (2023-08-29T09:10:53Z)
• ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms [5.478671305092084]
  We introduce ParlayANN, a library of deterministic and parallel graph-based approximate nearest neighbor search algorithms. We develop novel parallel implementations for four state-of-the-art graph-based ANNS algorithms that scale to billion-scale datasets.
  arXiv  Detail & Related papers  (2023-05-07T19:28:23Z)
• 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)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  Graph outlier detection is an emerging but crucial machine learning task with numerous applications. We present the first comprehensive unsupervised node outlier detection benchmark for graphs called UNOD.
  arXiv  Detail & Related papers  (2022-06-21T01:46:38Z)
• Providing Meaningful Data Summarizations Using Examplar-based Clustering in Industry 4.0 [67.80123919697971]
  We show, that our GPU implementation provides speedups of up to 72x using single-precision and up to 452x using half-precision compared to conventional CPU algorithms. We apply our algorithm to real-world data from injection molding manufacturing processes and discuss how found summaries help with steering this specific process to cut costs and reduce the manufacturing of bad parts.
  arXiv  Detail & Related papers  (2021-05-25T15:55:14Z)

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.