The DOI matches its Crossref record; 84 of the 84 references it cites were found in a registry or an index.
Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement
Abstract
Nearest neighbor search is a fundamental and essential operation in applications from many domains, such as databases, machine learning, multimedia, and computer vision. Because exact searching results are not efficient for a high-dimensional space, a lot of efforts have turned to approximate nearest neighbor search. Although many algorithms have been continuously proposed in the literature each year, there is no comprehensive evaluation and analysis of their performance. In this paper, we conduct a comprehensive experimental evaluation of many state-of-the-art methods for approximate nearest neighbor search. Our study (1) is cross-disciplinary (i.e., including 19 algorithms in different domains, and from practitioners) and (2) has evaluated a diverse range of settings, including 20 datasets, several evaluation metrics, and different query workloads. The experimental results are carefully reported and analyzed to understand the performance results. Furthermore, we propose a new method that achieves both high query efficiency and high recall empirically on majority of the datasets under a wide range of settings.
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.
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
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
(1999) · Cited by 3,186
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 3×
“(PQ) [5] is a popular methods for ANNS, which decomposes”
Locality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. S. (2004) · Proceedings of the twentieth annual symposium on Computational geometry · doi:10.1145/997817.997857 · Cited by 2,936
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,389
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
Gong, Y., Lazebnik, S., Gordo, A., & Perronnin, F. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.193 · Cited by 1,834
Kleinberg, J. M. (2000) · Nature · doi:10.1038/35022643 · Cited by 1,737
Gray, R. M., & Neuhoff, D. L. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720541 · Cited by 1,642
Scalable Nearest Neighbor Algorithms for High Dimensional Data
Muja, M., & Lowe, D. G. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2321376 · Cited by 1,407
Salakhutdinov, R., & Hinton, G. (2009) · International Journal of Approximate Reasoning · doi:10.1016/j.ijar.2008.11.006 · Cited by 1,246
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Andoni, A., & Indyk, P. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.49 · Cited by 1,067
(1993) · doi:10.5555/313559.313789 · Cited by 998
Wang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 971
Cover trees for nearest neighbor
Beygelzimer, A., Kakade, S., & Langford, J. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143857 · Cited by 813
A Branch and Bound Algorithm for Computing k-Nearest Neighbors
Fukunaga, K., & Narendra, P. M. (1975) · IEEE Transactions on Computers · doi:10.1109/t-c.1975.224297 · Cited by 736
Optimised KD-trees for fast image descriptor matching
Silpa-Anan, C., & Hartley, R. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587638 · Cited by 677
Efficient k-nearest neighbor graph construction for generic similarity measures
Dong, W., Moses, C., & Li, K. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963487 · Cited by 673
Multidimensional divide-and-conquer
Bentley, J. L. (1980) · Communications of the ACM · doi:10.1145/358841.358850 · Cited by 672
Multi-probe LSH: efficient indexing for high-dimensional similarity search
Lv, Q., Josephson, W. K., Wang, Z., Charikar, M., & Li, K. (2007) · Very Large Data Bases · Cited by 634
Liu, W., Mu, C., Kumar, S., & Chang, S. (2014) · neural information processing systems · Cited by 597
Deep hashing for compact binary codes learning
Liong, V. E., Lu, J., Wang, G., Moulin, P., & Zhou, J. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298862 · Cited by 545
An empirical evaluation of supervised learning in high dimensions
Caruana, R., Karampatziakis, N., & Yessenalina, A. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390169 · Cited by 524
Learning to Hash for Indexing Big Data—A Survey
Wang, J., Liu, W., Kumar, S., & Chang, S.-F. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2487976 · Cited by 519
Approximate nearest neighbor algorithm based on navigable small world graphs
Malkov, Y., Ponomarenko, A., Logvinov, A., & Krylov, V. (2014) · Information Systems · doi:10.1016/j.is.2013.10.006 · Cited by 419
Unsupervised Deep Hashing with Similarity-Adaptive and Discrete Optimization
Shen, F., Xu, Y., Liu, L., Yang, Y., Huang, Z., & Shen, H. T. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2789887 · Cited by 407
Optimized Product Quantization
Ge, T., He, K., Ke, Q., & Sun, J. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.240 · Cited by 391
Random projection trees and low dimensional manifolds
Dasgupta, S., & Freund, Y. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374452 · Cited by 375
Differentially Private High-Dimensional Approximate Range Counting, Revisited
Wang, J., Shen, H. T., Song, J., & Ji, J. (2014) · arXiv (Cornell University) · doi:10.4230/lipics.cpm.2023.20 · Cited by 370
Learning Compact Binary Descriptors with Unsupervised Deep Neural Networks
Lin, K., Lu, J., Chen, C.-S., & Zhou, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.133 · Cited by 363
Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data
RadovanovićMiloš, NanopoulosAlexandros, & IvanovićMirjana (2010) · Journal of Machine Learning Research · doi:10.5555/1756006.1953015 · Cited by 334
Searching in one billion vectors: Re-rank with source coding
Jegou, H., Tavenard, R., Douze, M., & Amsaleg, L. (2011) · 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2011.5946540 · Cited by 313
Kong, W., & Li, W.-J. (2012) · neural information processing systems · Cited by 306
Self-citationNorouzi, M., & Fleet, D. J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.388 · Cited by 298
Additive Quantization for Extreme Vector Compression
Babenko, A., & Lempitsky, V. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.124 · Cited by 278
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search
Kalantidis, Y., & Avrithis, Y. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.298 · Cited by 275
Searching in metric spaces by spatial approximation
Navarro, G. (2002) · The VLDB Journal The International Journal on Very Large Data Bases · doi:10.1007/s007780200060 · Cited by 272
Locality-sensitive hashing scheme based on dynamic collision counting
Gan, J., Feng, J., Fang, Q., & Ng, W. (2012) · Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2213836.2213898 · Cited by 237
Quality and efficiency in high dimensional nearest neighbor search
Tao, Y., Yi, K., Sheng, C., & Kalnis, P. (2009) · Proceedings of the 2009 ACM SIGMOD International Conference on Management of data · doi:10.1145/1559845.1559905 · Cited by 230
Query-aware locality-sensitive hashing for approximate nearest neighbor search
Huang, Q., Feng, J., Zhang, Y., Fang, Q., & Ng, W. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2850469.2850470 · Cited by 213
Self-citationAnalyzing and Modeling the Maximum Diversity Problem by Zero‐One Programming*
Kuo, C., Glover, F., & Dhir, K. S. (1993) · Decision Sciences · doi:10.1111/j.1540-5915.1993.tb00509.x · Cited by 211
Babenko, A., & Lempitsky, V. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6248038 · Cited by 200
Composite Quantization for Approximate Nearest Neighbor Search
Zhang, T., Du, C., & Wang, J. (2014) · Cited by 191
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Andoni, A., & Razenshteyn, I. (2015) · Proceedings of the forty-seventh annual ACM symposium on Theory of Computing · doi:10.1145/2746539.2746553 · Cited by 185
Learning to Hash with Binary Deep Neural Network
Do, T.-T., Doan, A.-D., & Cheung, N.-M. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46454-1_14 · Cited by 184
Hashing with binary autoencoders
Carreira-Perpiñán, M. Á., & Raziperchikolaei, R. (2015) · 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.2015.7298654 · Cited by 181
Entropy based nearest neighbor search in high dimensions
Panigrahy, R. (2006) · doi:10.5555/1109557.1109688 · Cited by 181
Malkov, Y. A., & Yashunin, D. A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.09320 · Cited by 176
Estimating Local Intrinsic Dimensionality
Amsaleg, L., Chelly, O., Furon, T., Girard, S., Houle, M. E., Kawarabayashi, K., & Nett, M. (2015) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2783258.2783405 · Cited by 161
A posteriori multi-probe locality sensitive hashing
Joly, A., & Buisson, O. (2008) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/1459359.1459388 · Cited by 159
Scalable similarity search with optimized kernel hashing
He, J., Liu, W., & Chang, S. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835946 · Cited by 151
Joly, A., & Buisson, O. (2011) · 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.2011.5995709 · Cited by 150
Sun, Y., Wang, W., Qin, J., Zhang, Y., & Lin, X. (2014) · Proceedings of the VLDB Endowment · doi:10.14778/2735461.2735462 · Cited by 148
Self-citationScalable k-NN graph construction for visual descriptors
Wang, J., Wang, J., Zeng, G., Tu, Z., Gan, R., & Li, S. (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.6247790 · Cited by 146
Learning Hash Codes with Listwise Supervision
Wang, J., Liu, W., Sun, X. A., & Jiang, Y. (2013) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2013.377 · Cited by 146
Deep Hashing for Scalable Image Search
Lu, J., Liong, V. E., & Zhou, J. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2678163 · Cited by 134
Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
Terasawa, K., & Tanaka, Y. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73951-7_4 · Cited by 124
Order preserving hashing for approximate nearest neighbor search
Wang, J., Wang, J., Yu, N., & Li, S. (2013) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/2502081.2502100 · Cited by 120
Entropy based nearest neighbor search in high dimensions
Panigrahy, R. (2006) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1145/1109557.1109688 · Cited by 117
Tree quantization for large-scale similarity search and classification
Babenko, A., & Lempitsky, V. (2015) · 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.2015.7299052 · Cited by 110
EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN GraphPreprint
Fu, C., & Cai, D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.07228 · Cited by 107
Fast nearest neighbor retrieval for bregman divergences
Cayton, L. (2008) · International Conference on Machine Learning · doi:10.1145/1390156.1390171 · Cited by 106
Beyond Locality–Sensitive Hashing
Andoni, A., Indyk, P., Ên, H. L. N., & Razenshteyn, I. (2013) · Cited by 105
Fast kNN Graph Construction with Locality Sensitive Hashing
Zhang, Y., Huang, K., Geng, G., & Liu, C. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40991-2_42 · Cited by 93
Self-citationBeyond Locality-Sensitive Hashing
Andoni, A., Indyk, P., Nguyễn, H. L., & Razenshteyn, I. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973402.76 · Cited by 83
LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index
Zheng, Y., Guo, Q., Tung, A. K. H., & Wu, S. (2016) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2882903.2882930 · Cited by 82
Complementary Projection Hashing
Jin, Z., Hu, Y., Lin, Y., Zhang, D., Lin, S., Cai, D., & Li, X. (2013) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2013.39 · Cited by 72
Xia, Y., He, K., Wen, F., & Sun, J. Z. (2013) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2013.424 · Cited by 67
Lin, Y., Jin, R., Cai, D., Yan, S., & Li, X. (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.64 · Cited by 64
Gao, J., Jagadish, H. V., Lü, W., & Ooi, B. C. (2014) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2588555.2588565 · Cited by 59
Rank-Based Similarity Search: Reducing the Dimensional Dependence
Houle, M. E., & Nett, M. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2343223 · Cited by 56
Fast and Accurate Hashing Via Iterative Nearest Neighbors Expansion
Jin, Z., Zhang, D., Hu, Y., Lin, S., Cai, D., & He, X. (2014) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2014.2302018 · Cited by 52
Permutation search methods are efficient, yet faster search is possible
Naidan, B., Boytsov, L., & Nyberg, E. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2824032.2824059 · Cited by 48
On the Difficulty of Nearest Neighbor SearchPreprint
He, J., Kumar, S., & Chang, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.6411 · Cited by 47
Park, Y., Cafarella, M., & Mozafari, B. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2850583.2850589 · Cited by 35
Gao, J., Jagadish, H. V., Ooi, B. C., & Wang, S. (2015) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2783258.2783284 · Cited by 30
Unsupervised Deep Video Hashing with Balanced Rotation
Wu, G., Liu, L., Guo, Y., Ding, G., Han, J., Shen, J., & Shao, L. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/429 · Cited by 28
Unsupervised deep hashing for large-scale visual search
Xia, Z., Feng, X., Peng, J., & Hadid, A. (2016) · International Conference on Image Processing Theory, Tools and Applications (IPTA) · doi:10.1109/ipta.2016.7821007 · Cited by 27
Learning to Prune in Metric and Non-Metric Spaces
Boytsov, L., & Naidan, B. (2013) · Cited by 17
Intelligent probing for locality sensitive hashing
Lv, Q., Josephson, W. K., Wang, Z., Charikar, M., & Li, K. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3137765.3137836 · Cited by 13
A Revisit on Deep Hashings for Large-scale Content Based Image RetrievalPreprint
Cai, D., Gu, X., & Wang, C. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.06016 · Cited by 13
Discrete Hashing with Deep Neural NetworkPreprint
Do, T.-T., Doan, A.-Z., & Cheung, N. M. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1508.07148 · Cited by 9
Shortlist Selection with Residual-Aware Distance Estimator for K-Nearest Neighbor Search
Heo, J., Lin, Z., Shen, X., Brandt, J., & Yoon, S. (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.221 · Cited by 9
High-dimensional similarity search for large datasets
Li, K., & Dong, W. (2011) · Cited by 8
Cited by
Halder, R. K., Uddin, M. N., Uddin, M. A., Aryal, S., & Khraisat, A. (2024) · Journal of Big Data · doi:10.1186/s40537-024-00973-y · Cited by 520
(2021) · doi:10.1145/3448016.3457550 · Cited by 416
Challenges in KNN Classification
Zhang, S. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3049250 · Cited by 362
Wang, M., Xu, X., Yue, Q., & Wang, Y. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3476249.3476255 · Cited by 264
Dense Text Retrieval Based on Pretrained Language Models: A Survey
Zhao, W. X., Liu, J., Ren, R., & Wen, J.-R. (2024) · ACM Transactions on Information Systems · doi:10.1145/3637870 · Cited by 211
Metadata
- Authors
- Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., & Lin, X.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2020-08-01
- Volume
- 32
- Issue
- 8
- Pages
- 1475-1488
- ISSN
- 1041-4347 (ISSN-L)
- 1558-2191
- 2326-3865
- OpenAlex
- W2963265099
- Cited by
- 454
- References
- 84
- FWCI
- 16.42
- Type
- journal article
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.