17027

Billion-scale similarity search with GPUs

Jeff Johnson, Matthijs Douze, Herve Jegou
Facebook AI Research
arXiv:1702.08734 [cs.CV], (28 Feb 2017)

@article{johnson2017billionscale,

   title={Billion-scale similarity search with GPUs},

   author={Johnson, Jeff and Douze, Matthijs and Jegou, Herve},

   year={2017},

   month={feb},

   archivePrefix={"arXiv"},

   primaryClass={cs.CV}

}

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.5x 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 for the sake of comparison and reproducibility.
VN:F [1.9.22_1171]
Rating: 3.0/5 (2 votes cast)
Billion-scale similarity search with GPUs, 3.0 out of 5 based on 2 ratings

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: