Cited by 4,228Advanced Image and Video Retrieval TechniquesParallel Computing and Optimization TechniquesGraph Theory and Algorithms

Billion-scale similarity search with GPUs

Open access
Johnson, Jeff, Douze, Matthijs, Jegou, Herve·2021·IEEE Transactions on Big Data

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/tbdata.2019.2921572

Cites

62 of 62 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Vector-indexed stores scale to millions of records but lose structured relationships; they support similarity queries but not causal queries.

    “They scale gracefully to millions of records but lose structured relationships: you can ask 'what's most similar?' but not 'what caused what?'”

    From Memory for Autonomous LLM Agents:Mechanisms, Evaluation, and Emerging Frontiers (2026) · cites this paper as Johnson et al., 2021

    The Introduction (page unavailable) describes similarity search on billion-scale vector databases and says that, for the applications discussed, numerical similarity is more suitable than searching via structured relations. It does not say that vector indexes lose structured relationships or establish that they cannot answer causal queries. (LLM, conf=0.86)

    Experimental — accuracy not yet measured
  • Dense passage retrieval via learned encoders, typically backed by FAISS-style approximate nearest-neighbor search, remains the default implementation, often augmented with sparse BM25 and metadata filters.

    “Dense passage retrieval [Karpukhin et al., 2020] via learned encoders, typically backed by FAISS-style approximate nearest-neighbor search [Johnson et al., 2021], remains the default implementation, often augmented with sparse BM25 and metadata filters (timestamps, tool types, task tags).”

    From Memory for Autonomous LLM Agents:Mechanisms, Evaluation, and Emerging Frontiers (2026) · cites this paper as Johnson et al., 2021

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

3 of the 65 references couldn’t be matched to a known paper.

Research works printed but not linked: 3

  1. [29]29. F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992.
  2. [42]42. B. Thomee, D. A. Shamma, G. Friedland, B. Elizalde, K. Ni, D. Poland, D. Borth, and L.-J. Li. YFCC100M: The new data in multimedia research. Communications of the ACM, 59(2):64-73, January 2016.
  3. [46]46. R. Weber, H.-J. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proc. International Conference on Very Large DataBases, pages 194-205, 1998.

Cited by

Sorted by citations

Authors
Johnson, J., Douze, M., & Jegou, H.
Affiliations
Meta (United States) (US)
Venue
IEEE Transactions on Big Data
Published
2021-07-01
Volume
7
Issue
3
Pages
535-547
ISSN
  • 2332-7790 (ISSN-L)
  • 2372-2096
OpenAlex
W2593864460
Cited by
4,228
References
65
Citations by year
2026: 973 · 2025: 691 · 2024: 565 · 2023: 677 · 2022: 446 · 2021: 432 · 2020: 231 · 2019: 125 · 2018: 71 · 2017: 17
FWCI
136.66
Type
journal article
Language
en
Open access
Locations
  • IEEE Transactions on Big Data (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Image and Video Retrieval Techniques
  • Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
Keywords
similarity search, nearest neighbor search, GPU acceleration, product quantization, approximate nearest neighbor search, high-dimensional indexing, image retrieval, memory hierarchy, parallel algorithms

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review