Elamur Research
☰
home / papers / 2017 / Billion-scale similarity search with GPUs

Billion-scale similarity search with GPUs

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1702.08734

Summary

Searching huge collections of embedding vectors (image or text features with tens to thousands of dimensions) for their nearest neighbours is expensive. GPUs should help, but earlier GPU methods were held back by steps with little parallelism, especially selecting the k smallest distances, and by poor use of memory. The authors (Facebook AI Research) built a k-selection routine that keeps its working data in GPU registers and can be fused with other kernels. On top of it, they designed GPU layouts for exact brute-force search and for compressed approximate search with product quantization (IVFADC). They tested the system on standard benchmarks (Sift1M, Sift1B, Deep1B) and on 95 million Yfcc100M images. In every setting it clearly beat earlier GPU and CPU results, and it made billion-scale k-NN graph construction practical on one machine with a few GPUs. The code was released as the open-source library Faiss, which became a standard tool for vector search.

Key points

  • The k-selection kernel reaches up to 55% of the GPU's theoretical peak. The resulting search runs 8.5× faster than the previous best GPU method (Wieschollek et al.).
  • On Sift1B with 8-byte codes on one GPU, the method gets R@10 = 0.376 at 17.7 µs per query, compared with 0.35 at 150 µs before. On Sift1M, at the same time budget, R@1 rises from 0.51 to 0.80.
  • On Deep1B using 4 GPUs, it reaches R@1 ≈ 0.45 at 0.0133 ms per vector. The reference single-thread CPU result needed 20 ms for similar recall.
  • A 10-NN graph over 95M Yfcc100M images (ResNet features reduced to 128-d with PCA) was built in 35 minutes with accuracy above 0.8. Building one over 1 billion Deep1B vectors needed less than 12 hours using four Titan X GPUs of the Maxwell generation.
  • The implementation is open source as Faiss (github.com/facebookresearch/faiss).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cited by

855 papers of our library cite it (of the 140673 whose bibliographies we read); 37 of them have a page here, 818 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1702.08734 · arXiv 1702.08734

@misc{johnson2017billion,
  title = {{Billion-scale similarity search with GPUs}},
  author = {Johnson, Jeff and Douze, Matthijs and Jégou, Hervé},
  year = {2017},
  doi = {10.48550/arxiv.1702.08734},
  eprint = {1702.08734},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1702.08734}
}

References

48 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. T. Alabi, J. D. Blanchard, B. Gordon, and R. Steinbach. Fast k-selection algorithms for graphics processing units. ACM Journal of Experimental Algorithmics, 17:4.2:4.1–4.2:4.29, October 2012. find
  2. F. André, A.-M. Kermarrec, and N. L. Scouarnec. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. In Proc. International Conference on Very Large DataBases, pages 288–299, 2015. find
  3. Y. Avrithis, Y. Kalantidis, E. Anagnostopoulos, and I. Z. Emiris. Web-scale image clustering revisited. In Proc. International Conference on Computer Vision, pages 1502–1510, 2015. find
  4. A. Babenko and V. Lempitsky. The inverted multi-index. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 3069–3076, June 2012. find
  5. A. Babenko and V. Lempitsky. Improving bilayer product quantization for billion-scale approximate nearest neighbors in high dimensions. arXiv preprint arXiv:1404.1831, 2014. — [arXiv:1404.1831](https://arxiv.org/abs/1404.1831) find
  6. A. Babenko and V. Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 2055–2063, June 2016. find
  7. R. Barrientos, J. Gómez, C. Tenllado, M. Prieto, and M. Marin. knn query processing in metric spaces using GPUs. In International European Conference on Parallel and Distributed Computing, volume 6852 of Lecture Notes (12) in Computer Science, pages 380–392, Bordeaux, France, September 2011. Spring… find
  8. K. E. Batcher. Sorting networks and their applications. In Proc. Spring Joint Computer Conference, AFIPS ’68 (Spring), pages 307–314, New York, NY, USA, 1968. ACM. find
  9. P. Boncz, W. Lehner, and T. Neumann. Special issue: Modern hardware. The VLDB Journal, 25(5):623–624, 2016. find
  10. J. Canny, D. L. W. Hall, and D. Klein. A multi-teraflop constituency parser using GPUs. In Proc. Empirical Methods on Natural Language Processing, pages 1898–1907. ACL, 2013. find
  11. J. Canny and H. Zhao. Bidmach: Large-scale learning with zero memory allocation. In BigLearn workshop, NIPS, 2013. find
  12. B. Catanzaro, A. Keller, and M. Garland. A decomposition for in-place matrix transposition. In Proc. ACM Symposium on Principles and Practice of Parallel Programming, PPoPP ’14, pages 193–206, 2014. find
  13. J. Chhugani, A. D. Nguyen, V. W. Lee, W. Macy, M. Hagog, Y.-K. Chen, A. Baransi, S. Kumar, and P. Dubey. Efficient implementation of sorting on multi-core simd cpu architecture. Proc. VLDB Endow., 1(2):1313–1324, August 2008. find
  14. A. Dashti. Efficient computation of k-nearest neighbor graphs for large high-dimensional data sets on gpu clusters. Master’s thesis, University of Wisconsin Milwaukee, August 2013. find
  15. W. Dong, M. Charikar, and K. Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW: Proceeding of the International Conference on World Wide Web, pages 577–586, March 2011. find
  16. M. Douze, H. Jégou, and F. Perronnin. Polysemous codes. In Proc. European Conference on Computer Vision, pages 785–801. Springer, October 2016. find
  17. T. Ge, K. He, Q. Ke, and J. Sun. Optimized product quantization. IEEE Trans. PAMI, 36(4):744–755, 2014. find
  18. Y. Gong and S. Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 817–824, June 2011. find
  19. Y. Gong, L. Wang, R. Guo, and S. Lazebnik. Multi-scale orderless pooling of deep convolutional activation features. In Proc. European Conference on Computer Vision, pages 392–407, 2014. find
  20. A. Gordo, J. Almazan, J. Revaud, and D. Larlus. Deep image retrieval: Learning global representations for image search. In Proc. European Conference on Computer Vision, pages 241–257, 2016. find
  21. S. Han, H. Mao, and W. J. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149, 2015. find
  22. K. He, F. Wen, and J. Sun. K-means hashing: An affinity-preserving quantization method for learning binary compact codes. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 2938–2945, June 2013. find
  23. K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 770–778, June 2016. find
  24. X. He, D. Agarwal, and S. K. Prasad. Design and implementation of a parallel priority queue on many-core architectures. IEEE International Conference on High Performance Computing, pages 1–10, 2012. find
  25. H. Jégou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Trans. PAMI, 33(1):117–128, January 2011. find
  26. H. Jégou, R. Tavenard, M. Douze, and L. Amsaleg. Searching in one billion vectors: re-rank with source coding. In International Conference on Acoustics, Speech, and Signal Processing, pages 861–864, May 2011. find
  27. Y. Kalantidis and Y. Avrithis. Locally optimized product quantization for approximate nearest neighbor search. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 2329–2336, June 2014. find
  28. A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, pages 1097–1105, 2012. find
  29. F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992. find
  30. E. Lindholm, J. Nickolls, S. Oberman, and J. Montrym. NVIDIA Tesla: a unified graphics and computing architecture. IEEE Micro, 28(2):39–55, March 2008. find
  31. W. Liu and B. Vinter. Ad-heap: An efficient heap data structure for asymmetric multicore processors. In Proc. of Workshop on General Purpose Processing Using GPUs, pages 54:54–54:63. ACM, 2014. find
  32. T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, pages 3111–3119, 2013. find
  33. L. Monroe, J. Wendelberger, and S. Michalak. Randomized selection on the GPU. In Proc. ACM Symposium on High Performance Graphics, pages 89–98, 2011. find
  34. M. Norouzi and D. Fleet. Cartesian k-means. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 3017–3024, June 2013. find
  35. M. Norouzi, A. Punjani, and D. J. Fleet. Fast search in Hamming space with multi-index hashing. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 3108–3115, 2012. find
  36. J. Pan and D. Manocha. Fast GPU-based locality sensitive hashing for k-nearest neighbor computation. In Proc. ACM International Conference on Advances in Geographic Information Systems, pages 211–220, 2011. find
  37. L. Paulevé, H. Jégou, and L. Amsaleg. Locality sensitive hashing: a comparison of hash function types and querying mechanisms. Pattern recognition letters, 31(11):1348–1358, August 2010. find
  38. O. Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems, pages 163–171, 2014. find
  39. A. Sharif Razavian, H. Azizpour, J. Sullivan, and S. Carlsson. CNN features off-the-shelf: an astounding baseline for recognition. In CVPR workshops, pages 512–519, 2014. find
  40. N. Sismanis, N. Pitsianis, and X. Sun. Parallel search of k-nearest neighbors with synchronous operations. In IEEE High Performance Extreme Computing Conference, pages 1–6, 2012. find
  41. X. Tang, Z. Huang, D. M. Eyers, S. Mills, and M. Guo. Efficient selection algorithm for fast k-nn search on GPUs. In IEEE International Parallel & Distributed Processing Symposium, pages 397–406, 2015. find
  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. find
  43. V. Volkov and J. W. Demmel. Benchmarking GPUs to tune dense linear algebra. In Proc. ACM/IEEE Conference on Supercomputing, pages 31:1–31:11, 2008. find
  44. A. Wakatani and A. Murakami. GPGPU implementation of nearest neighbor search with product quantization. In IEEE International Symposium on Parallel and Distributed Processing with Applications, pages 248–253, 2014. find
  45. T. Warashina, K. Aoyama, H. Sawada, and T. Hattori. Efficient k-nearest neighbor graph construction using mapreduce for large-scale data sets. IEICE Transactions, 97-D(12):3142–3154, 2014. find
  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. find
  47. P. Wieschollek, O. Wang, A. Sorkine-Hornung, and H. P. A. Lensch. Efficient large-scale approximate nearest neighbor search on the GPU. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 2027–2035, June 2016. find
  48. S. Williams, A. Waterman, and D. Patterson. Roofline: An insightful visual performance model for multicore architectures. Communications of the ACM, 52(4):65–76, April 2009. find