Skip to content

Billion-Scale Similarity Search with GPUs

Jeff Johnson, Matthijs Douze, Hervé Jeǵou

IEEE Transactions on Big Data · 2019 · 5,134 citationsOpen access

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Johnson, J., Douze, M., & Jeǵou, H. (2019). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3), 535–547. https://doi.org/10.1109/tbdata.2019.2921572

In text: (Johnson et al., 2019)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

Abstract

Similarity search finds application in database systems handling complex data such as images or videos, which are typically represented by high-dimensional features and require specific indexing structures. This paper tackles the problem of better utilizing GPUs for this task. While GPUs excel at data parallel tasks such as distance computation, prior approaches in this domain are bottlenecked by algorithms that expose less parallelism, such ask-min selection, or make poor use of the memory hierarchy. We propose a novel design fork-selection. We apply it in different similarity search scenarios, by optimizing brute-force, approximate and compressed-domain search based on product quantization. In all these setups, we outperform the state of the art by large margins. Our implementation operates at up to 55 percent of theoretical peak performance, enabling a nearest neighbor implementation that is 8.5 × faster than prior GPU state of the art. It enables the construction of a high accuracyk-NN graph on 95 million images from the Yfcc100M dataset in 35 minutes, and of a graph connecting 1 billion vectors in less than 12 hours on 4 Maxwell Titan X GPUs. We have open-sourced our approach for the sake of comparison and reproducibility.

  1. A Formal Basis for the Heuristic Determination of Minimum Cost Paths1968
  2. A Comprehensive Survey on Graph Neural Networks2020
  3. The Graph Neural Network Model2008
  4. Graph neural networks: A review of methods and applications2020
  5. Depth-First Search and Linear Graph Algorithms1972

Metadata from OpenAlex (CC0). Citations are generated from the published record.