SONG: Approximate nearest neighbor search on GPU

Weijie Zhao, Shulong Tan, Ping Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020
PublisherIEEE Computer Society
Number of pages12
ISBN (Electronic)9781728129037
StatePublished - Apr 2020
Externally publishedYes
Event36th IEEE International Conference on Data Engineering, ICDE 2020 - Dallas, United States
Duration: Apr 20 2020Apr 24 2020

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference36th IEEE International Conference on Data Engineering, ICDE 2020
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'SONG: Approximate nearest neighbor search on GPU'. Together they form a unique fingerprint.

Cite this