Billion-scale similarity search with GPUs

Jeff Johnson

arXiv · PDF · Open in the Atlas

Code that ran

We lifted 35 functions out of this paper's own repositories and ran 8 of them in a sandbox. "Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results.

Repositories linked to this paper

• facebookresearch/faiss — marked official in Papers with Code; named in the paper
• CoderINusE/NIPS-implementation
• CoderINusE/unbounded-cache-lm
• NGDSystems/faiss
• NJU-yasuo/faiss_t
• PhilipBAdams/faiss-learned-termination-prior-weighted
• architecture-research-group/ae-asplo25-iks-faiss
• bitsun/faiss-windows
• gauenk/faiss_fork
• hartb/faiss-gpu-feedstock
• junjya/faiss
• mimbres/neural-audio-fp
• shiwendai/Faiss
• milvus-io/milvus

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

Similarity search finds application in specialized 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, prior approaches are bottlenecked by algorithms that expose less parallelism, such as k-min selection, or make poor use of the memory hierarchy. We propose a design for k-selection that operates at up to 55% of theoretical peak performance, enabling a nearest neighbor implementation that is 8.5× faster than prior GPU state of the art. We apply it in different similarity search scenarios, by proposing optimized design for 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 enables the construction of a high accuracy k-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 1 for the sake of comparison and reproducibility.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("1702.08734")
get_code_for_paper("1702.08734")
have("1702.08734")

Connect an agent — have() is free.