CoChat
Sign Up
PreprintCited by 4,140Advanced Image and Video Retrieval TechniquesParallel Computing and Optimization TechniquesGraph Theory and Algorithms

Billion-scale similarity search with GPUs

Open access
Johnson, Jeff, Douze, Matthijs, Jégou, Hervé·2017·arXiv
DOI 10.48550/arxiv.1702.08734arXiv 1702.08734
Open this paper in CoChat — free accountOpen PDF

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.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.

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

DataCite · 10.48550/arxiv.1702.08734

Cites

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?

  • By using optimized index structures, finding the most similar Quora question can be reduced from 50 hours to a few milliseconds.

    “By using optimized index structures, finding the most similar Quora question can be reduced from 50 hours to a few milliseconds (Johnson et al., 2017).”

    From Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks (2019) · cites this paper as Johnson et al., 2017

    The Abstract (page unavailable) says the paper proposes optimized similarity-search methods and reports speed improvements; Section 5.2 (page unavailable) describes its indexing approach. Our copy does not report a Quora-question search or a reduction from 50 hours to a few milliseconds (searched: Quora, 50 hours, milliseconds). (LLM, conf=0.85)

    Experimental — accuracy not yet measured

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

No references could be resolved yet.

Research works printed but not linked: 48

  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.
  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.
  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.
  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.
  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
  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.
  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 in Computer Science, pages 380-392, Bordeaux, France, September 2011. Springer.
  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.
  9. P. Boncz, W. Lehner, and T. Neumann. Special issue: Modern hardware. The VLDB Journal, 25(5):623-624, 2016.
  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.
  11. J. Canny and H. Zhao. Bidmach: Large-scale learning with zero memory allocation. In BigLearn workshop, NIPS, 2013.
  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.
  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.
  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.
  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.
  16. M. Douze, H. Jégou, and F. Perronnin. Polysemous codes. In Proc. European Conference on Computer Vision, pages 785-801. Springer, October 2016.
  17. T. Ge, K. He, Q. Ke, and J. Sun. Optimized product quantization. IEEE Trans. PAMI, 36(4):744-755, 2014.
  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.
  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.
  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.
  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. · arXiv
  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.
  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.
  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.
  25. H. Jégou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Trans. PAMI, 33(1):117-128, January 2011.
  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.
  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.
  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.
  29. F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992.
  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.
  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.
  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.
  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.
  34. M. Norouzi and D. Fleet. Cartesian k-means. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, pages 3017-3024, June 2013.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.

Cited by

Sorted by citations

Authors
Johnson, J., Douze, M., & Jégou, H.
Affiliations
Meta (United States) (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2017
Volume
7
Issue
3
Pages
535-547
ISSN
2332-7790 (ISSN-L)
DOI
10.48550/arxiv.1702.08734
arXiv
1702.08734
OpenAlex
W2593864460
Cited by
4,140
References
0
Citations by year
2026: 944 · 2025: 692 · 2024: 565 · 2023: 675 · 2022: 433 · 2021: 415 · 2020: 220 · 2019: 115 · 2018: 64 · 2017: 17
FWCI
132.58
Type
journal article
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
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