Lune

ICDE2020Top-tier venue

SONG: Approximate Nearest Neighbor Search on GPU

Weijie Zhao, Shulong Tan, Ping Li

Abstract

Approximate nearest neighbor (ANN) searching is a fundamental problem in computer science with numerous applications in (e.g.,) machine learning and data mining. Recent studies show that graph-based ANN methods often outperform other types of ANN algorithms. For typical graph-based methods, the searching algorithm is executed iteratively and the execution dependency prohibits GPU adaptations. In this paper, we present a novel framework that decouples the searching on graph algorithm into 3 stages, in order to parallel the performance-crucial distance computation. Furthermore, to obtain better parallelism on GPU, we propose novel ANN-specific optimization methods that eliminate dynamic GPU memory allocations and trade computations for less GPU memory consumption. The proposed system is empirically compared against HNSW–the state-of-the-art ANN method on CPU–and Faiss–the popular GPU-accelerated ANN platform–on 6 datasets. The results confirm the effectiveness: SONG has around 50-180x speedup compared with single-thread HNSW, while it substantially outperforms Faiss.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

50 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs cites A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
  • CXL-ANNS: Software-Hardware Collaborative Memory Disaggregation and Computation for Billion-Scale Approximate Nearest Neighbor Search cites A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
  • Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases cites A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
  • An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint cites A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers50

  1. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor SearchMengzhao Wang, Xiaoliang Xu, Qiang Yue, Yuxiang WangVLDB 2021 · 354 citations
  2. CXL-ANNS: Software-Hardware Collaborative Memory Disaggregation and Computation for Billion-Scale Approximate Nearest Neighbor SearchJunhyeok Jang, Hanjin Choi, Hanyeoreum Bae, Seungjun Lee et al.USENIX ATC 2023 · 75 citations
  3. Efficient Approximate Nearest Neighbor Search in Multi-dimensional DatabasesYun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang et al.SIGMOD 2023 · 74 citations
  4. An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute ConstraintMengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang et al.NeurIPS 2023 · 70 citations
  5. CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUsHiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang et al.ICDE 2024 · 59 citations

Related papers

  1. CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory DisaggregationChengying Huan, Renjie Yao, Shaonan Ma, Rong Gu et al.SIGMOD 2026
  2. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor SearchYutong Gou, Jianyang Gao, Yuexuan Xu, Cheng LongSIGMOD 2025 · 21 citations
  3. Disentangling Graph Dependencies for Efficient Billion-Scale GPU Vector SearchHaoru Zhao, Jingkai He, Jingyao Zeng, Mingkai Dong et al.OSDI 2026
  4. Accelerating High-Dimensional ANN Search via Skipping Redundant Distance ComputationsZiwen Song, Bin Wang, Xiaochun YangSIGMOD 2026 · 1 citation
  5. High-Throughput, Cost-Effective Billion-Scale Vector Search with a Single GPUHaodi Jiang, Hao Guo, Minhui Xie, Jiwu Shu et al.SIGMOD 2026
Dusk over the sea between two cliffs drawn in fine vertical lines