Billion-Scale Similarity Search with GPUs

The paper targets similarity search for complex, high-dimensional data such as images and videos, where specialized indexing structures are needed, and asks how to better exploit GPUs for this workload. The authors observe that although GPUs are well suited to data-parallel distance computation, earlier approaches were bottlenecked either by algorithms exposing little parallelism, such as k-min selection, or by poor use of the memory hierarchy. Their central contribution is a novel design for k-selection, which they apply across brute-force, approximate, and compressed-domain search based on product quantization.

Across all these settings the method outperforms the prior state of the art by large margins, running at up to 55 percent of theoretical peak performance and yielding a nearest-neighbor implementation roughly 8.5 times faster than the best previous GPU approach. In practice this enables constructing a high-accuracy k-NN graph over 95 million Yfcc100M images in 35 minutes and connecting one billion vectors in under 12 hours on four Maxwell Titan X GPUs, and the authors open-sourced their implementation for reproducibility.