The DOI matches its Crossref record; 62 of the 65 references it cites were found in a registry or an index.
Billion-Scale Similarity Search with GPUs
Open accessAbstract
Similarity search finds application in 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 such as distance computation, prior approaches in this domain are bottlenecked by algorithms that expose less parallelism, such ask-min selection, or make poor use of the memory hierarchy. We propose a novel design fork-selection. We apply it in different similarity search scenarios, by optimizing 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 operates at up to 55 percent of theoretical peak performance, enabling a nearest neighbor implementation that is 8.5 × faster than prior GPU state of the art. It enables the construction of a high accuracyk-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.
Overview
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.
Integrity signals
Registry
Cites
Statistics
Verification
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.
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“They scale gracefully to millions of records but lose structured relationships: you can ask 'what's most similar?' but not 'what caused what?'”
From Memory for Autonomous LLM Agents:Mechanisms, Evaluation, and Emerging Frontiers (2026) · cites this paper as Johnson et al., 2021
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“Dense passage retrieval [Karpukhin et al., 2020] via learned encoders, typically backed by FAISS-style approximate nearest-neighbor search [Johnson et al., 2021], remains the default implementation, often augmented with sparse BM25 and metadata filters (timestamps, tool types, task tags).”
From Memory for Autonomous LLM Agents:Mechanisms, Evaluation, and Emerging Frontiers (2026) · cites this paper as Johnson et al., 2021
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474
ImageNet classification with deep convolutional neural networks
Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2017) · Communications of the ACM · doi:10.1145/3065386 · Cited by 112,155
Distributed Representations of Words and Phrases and their Compositionality
Mikolov, T., Sutskever, I., Chen, K., Corrado, G., & Dean, J. (2013) · arXiv · doi:10.48550/arxiv.1310.4546 · Cited by 24,533
Han, S., Mao, H., & Dally, W. J. (2015) · arXiv · doi:10.48550/arxiv.1510.00149 · Cited by 4,662
Bag of Tricks for Efficient Text Classification
Joulin, A., Grave, E., Bojanowski, P., & Mikolov, T. (2017) · Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers · doi:10.18653/v1/e17-2068 · Cited by 4,545
CNN Features Off-the-Shelf: An Astounding Baseline for Recognition
Razavian, A. S., Azizpour, H., Sullivan, J., & Carlsson, S. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition Workshops · doi:10.1109/cvprw.2014.131 · Cited by 4,451
Product Quantization for Nearest Neighbor Search
Jégou, H., Douze, M., & Schmid, C. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.57 · Cited by 2,956 · cited 5×
“ing a minimal accuracy loss results in orders of magnitude of compression [21]. The most popular vector compression methods can be classied into either binary codes [18, 22], or quantization methods [25, 37]. Both have the desirable property that searching neighbors does not require reconstructing the vectors. Our pap…”
BackgroundMethodInfluentialSelf-citationWilliams, S., Waterman, A., & Patterson, D. A. (2009) · Communications of the ACM · doi:10.1145/1498765.1498785 · Cited by 2,798
Deep Clustering for Unsupervised Learning of Visual Features
Caron, M., Bojanowski, P., Joulin, A., & Douze, M. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-01264-9_9 · Cited by 2,674
Self-citationSorting networks and their applications
Batcher, K. E. (1968) · doi:10.1145/1468075.1468121 · Cited by 2,442
Malkov, Y. A., & Yashunin, D. A. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2889473 · Cited by 1,904
Thomée, B., Shamma, D. A., Friedland, G. H., Elizalde, B., Ni, K. S., Poland, D., Borth, D., & Li, L.-J. (2016) · Communications of the ACM · doi:10.1145/2812802 · Cited by 1,715
NVIDIA Tesla: A Unified Graphics and Computing Architecture
Lindholm, E., Nickolls, J. R., Oberman, S. F., & Montrym, J. S. (2008) · IEEE Micro · doi:10.1109/mm.2008.31 · Cited by 1,364
Iterative quantization: A procrustean approach to learning binary codes
Gong, Y., & Lazebnik, S. (2011) · doi:10.1109/cvpr.2011.5995432 · Cited by 1,089
Multi-scale Orderless Pooling of Deep Convolutional Activation Features
Gong, Y., Wang, L., Guo, R., & Lazebnik, S. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10584-0_26 · Cited by 1,057
Learning to Hash with Binary Reconstructive Embeddings
Kulis, B., & Darrell, T. (2009) · Cited by 806
Deep Image Retrieval: Learning Global Representations for Image Search
Gordo, A., Almazán, J., Revaud, J., & Larlus, D. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46466-4_15 · Cited by 787
Particular object retrieval with integral max-pooling of CNN activations
Tolias, G., Sicre, R., & Jégou, H. (2015) · arXiv · doi:10.48550/arxiv.1511.05879 · Cited by 744
Benchmarking GPUs to tune dense linear algebra
Volkov, V. M., & Demmel, J. W. (2008) · doi:10.5555/1413370.1413402 · Cited by 715
Efficient k-nearest neighbor graph construction for generic similarity measures
Dong, W., Charikar, M., & Li, K. (2011) · International World Wide Web Conference (WWW) · doi:10.1145/1963405.1963487 · Cited by 703
Aggregating Local Deep Features for Image Retrieval
Yandex, A. B., & Lempitsky, V. (2015) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.150 · Cited by 679
Similarity estimation techniques from rounding algorithms
Charikar, M. (2002) · doi:10.1145/509961.509965 · Cited by 662
Word translation without parallel data
Lample, G., Conneau, A., Ranzato, M., Denoyer, L., & Jeǵou, H. (2018) · International Conference on Learning Representations · Cited by 653
Fast approximate nearest neighbor search with the navigating spreading-out graph
Fu, C., Xiang, C. J., Wang, C., & Cai, D. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3303753.3303754 · Cited by 554
Benchmarking GPUs to tune dense linear algebra
Volkov, V. M., & Demmel, J. (2008) · 2012 International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc.2008.5214359 · Cited by 489
Optimized Product Quantization
Ge, T., He, K., Ke, Q., & Sun, J. Z. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.240 · Cited by 435
K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
He, K., Wen, F., & Sun, J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.378 · Cited by 395
Searching in one billion vectors: Re-rank with source coding
Jeǵou, H., Tavenard, R., Douze, M., & Amsaleg, L. (2011) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2011.5946540 · Cited by 317
Self-citationNorouzi, M., & Fleet, D. J. (2013) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2013.388 · Cited by 306
Locality sensitive hashing: A comparison of hash function types and querying mechanisms
Paulevé, L., Jeǵou, H., & Amsaleg, L. (2010) · Pattern Recognition Letters · doi:10.1016/j.patrec.2010.04.004 · Cited by 298
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search
Kalantidis, Y., & Avrithis, Y. (2014) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2014.298 · Cited by 291
Fast search in Hamming space with multi-index hashing
Norouzi, M., Punjani, A., & Fleet, D. J. (2012) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2012.6248043 · Cited by 263
Efficient implementation of sorting on multi-core SIMD CPU architecture
Chhugani, J., Nguyen, A. D., Lee, V. W., Macy, W., Hagog, M., Chen, Y.-K., Baransi, A., Kumar, S., & Dubey, P. K. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454171 · Cited by 232
Babenko, A., & Lempitsky, V. (2012) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2012.6248038 · Cited by 216
Efficient Indexing of Billion-Scale Datasets of Deep Descriptors
Yandex, A. B., & Lempitsky, V. (2016) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2016.226 · Cited by 189
Low-Shot Learning with Large-Scale Diffusion
Douze, M., Szlam, A. D., Hariharan, B., & Jeǵou, H. (2018) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2018.00353 · Cited by 130
Self-citationFast GPU-based locality sensitive hashing for k-nearest neighbor computation
Pan, J., & Manocha, D. (2011) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/2093973.2094002 · Cited by 122
Asymmetric Distances for Binary Embeddings
Gordo, A., Perronnin, F., Gong, Y., & Lazebnik, S. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.101 · Cited by 116
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and EstimationPreprint
Shamir, O. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.3494 · Cited by 76
Deep Image Retrieval: Learning global representations for image searchPreprint
Gordo, A., Almazán, J., Revaud, J., & Larlus, D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.01325 · Cited by 76
André, F., Kermarrec, A.-M., & Scouarnec, N. L. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2856318.2856324 · Cited by 72
kNN Query Processing in Metric Spaces Using GPUs
Barrientos, R. J., Gómez, J. I., Tenllado, C., Prieto, M., & Marı́n, M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23400-2_35 · Cited by 57
Efficient Large-Scale Approximate Nearest Neighbor Search on the GPU
Wieschollek, P., Wang, O., Sorkine‐Hornung, A., & Lensch, H. P. A. (2016) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2016.223 · Cited by 55
Parallel search of k-nearest neighbors with synchronous operations
Sismanis, N., Pitsianis, N. P., & Sun, X. (2012) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2012.6408667 · Cited by 54
Douze, M., Jeǵou, H., & Perronnin, F. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46475-6_48 · Cited by 46
Self-citationFast k -selection algorithms for graphics processing units
Alabi, T., Blanchard, J. D., Gordon, B., & Steinbach, R. (2012) · ACM Journal of Experimental Algorithmics · doi:10.1145/2133803.2345676 · Cited by 43
A decomposition for in-place matrix transposition
Catanzaro, B., Keller, A., & Garland, M. (2014) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2555243.2555253 · Cited by 40
Web-Scale Image Clustering Revisited
Avrithis, Y., Kalantidis, Y., Anagnostopoulos, E., & Emiris, I. Z. (2015) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.176 · Cited by 35
Searching in one billion vectors: re-rank with source codingPreprint
Jeǵou, H., Tavenard, R., Douze, M., et al. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1102.3828 · Cited by 34
Self-citationBIDMach: Large-scale Learning with Zero Memory Allocation
Canny, J., & Zhao, H. (2013) · Cited by 30
Randomized selection on the GPU
Monroe, L., Wendelberger, J. R., & Michalak, S. (2011) · doi:10.1145/2018323.2018338 · Cited by 26
Design and implementation of a parallel priority queue on many-core architectures
He, X. Q., Agarwal, D., & Prasad, S. K. (2012) · International Conference on High Performance Computing (HiPC) · doi:10.1109/hipc.2012.6507490 · Cited by 23
Dashti, A., Komarov, I. I., & D’Souza, R. M. (2013) · PLoS ONE · doi:10.1371/journal.pone.0074113 · Cited by 20
A Multi-Teraflop Constituency Parser using GPUs
Canny, J., Hall, D., & Klein, D. (2013) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/d13-1195 · Cited by 19
Babenko, A., & Lempitsky, V. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.1831 · Cited by 18
Efficient Selection Algorithm for Fast k-NN Search on GPUs
Tang, X., Huang, Z., Eyers, D. M., Mills, S. J., & Guo, M. (2015) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2015.115 · Cited by 17
Efficient K-Nearest Neighbor Graph Construction Using MapReduce for Large-Scale Data Sets
WARASHINA, T., AOYAMA, K., Sawada, H., & Hattori, T. (2014) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2014edp7108 · Cited by 10
GPGPU Implementation of Nearest Neighbor Search with Product Quantization
Wakatani, A., & Murakami, A. (2014) · IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA) · doi:10.1109/ispa.2014.42 · Cited by 7
An Evaluation of Large-scale Methods for Image Instance and Class Discovery
Douze, M., Jeǵou, H., & Johnson, J. (2017) · Thematic Workshops of ACM Multimedia · doi:10.1145/3126686.3126711 · Cited by 6
Self-citationSpecial Issue: Modern Hardware
Boncz, P. A., Lehner, W., & Neumann, T. (2016) · The VLDB Journal · doi:10.1007/s00778-016-0440-7 · Cited by 3
Dashti, A. (2013) · UWM Digital Commons (University of Wisconsin–Milwaukee) · Cited by 2
ad-heap: an Efficient Heap Data Structure for Asymmetric Multicore Processors
Liu, W., & Vinter, B. (2014) · Research at the University of Copenhagen (University of Copenhagen) · Cited by 1
Research works printed but not linked: 3
- leighton, 1992, Introduction to Parallel Algorithms and Architectures Array Trees Hypercubes
- andoni, 2006, Near-optimal hashing algorithms for near neighbor problem in high dimensions, Proc Symp Foundations Comput Sci, 459
- weber, 1998, A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces, Proc Int Conf Very Large Databases, 194
Cited by
Sorted by citations
Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks
Reimers, N., & Gurevych, I. (2019) · Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) · doi:10.18653/v1/d19-1410 · Cited by 12,778
Rives, A., Meier, J., Sercu, T., Goyal, S., Lin, Z., Liu, J., Guo, D., Ott, M., Zitnick, C. L., Ma, J., et al. (2021) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2016239118 · Cited by 3,286
Dense passage retrieval for open-domain question answering
Karpukhin, V., Oguz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., & Yih, W.-T. (2020) · Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2020.emnlp-main.550 · Cited by 3,575
Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W.-T., Rocktäschel, T., et al. (2020) · arXiv · doi:10.48550/arxiv.2005.11401 · Cited by 3,101
On the Opportunities and Risks of Foundation Models
Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al. (2021) · arXiv · doi:10.48550/arxiv.2108.07258 · Cited by 2,676
Metadata
- Authors
- Johnson, J., Douze, M., & Jegou, H.
- Affiliations
- Meta (United States) (US)
- Venue
- IEEE Transactions on Big Data
- Published
- 2021-07-01
- Volume
- 7
- Issue
- 3
- Pages
- 535-547
- ISSN
- 2332-7790 (ISSN-L)
- 2372-2096
- OpenAlex
- W2593864460
- Cited by
- 4,228
- References
- 65
- Citations by year
- 2026: 973 · 2025: 691 · 2024: 565 · 2023: 677 · 2022: 446 · 2021: 432
- FWCI
- 136.66
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- 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 › Computational Theory and Mathematics › 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
