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

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020
PublisherIEEE Computer Society
Pages1033-1044
Number of pages12
ISBN (Electronic)9781728129037
DOIs
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
Volume2020-April
ISSN (Print)1084-4627

Conference

Conference36th IEEE International Conference on Data Engineering, ICDE 2020
Country/TerritoryUnited States
CityDallas
Period4/20/204/24/20

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

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

Cite this