The DOI matches its Crossref record; 81 of the 81 references it cites were found in a registry or an index.
A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search
Open accessAbstract
Approximate nearest neighbor search (ANNS) constitutes an important operation in a multitude of applications, including recommendation systems, information retrieval, and pattern recognition. In the past decade, graph-based ANNS algorithms have been the leading paradigm in this domain, with dozens of graph-based ANNS algorithms proposed. Such algorithms aim to provide effective, efficient solutions for retrieving the nearest neighbors for a given query. Nevertheless, these efforts focus on developing and optimizing algorithms with different approaches, so there is a real need for a comprehensive survey about the approaches' relative performance, strengths, and pitfalls. Thus here we provide a thorough comparative analysis and experimental evaluation of 13 representative graph-based ANNS algorithms via a new taxonomy and fine-grained pipeline. We compared each algorithm in a uniform test environment on eight real-world datasets and 12 synthetic datasets with varying sizes and characteristics. Our study yields novel discoveries, offerings several useful principles to improve algorithms, thus designing an optimized method that outperforms the state-of-the-art algorithms. This effort also helped us pinpoint algorithms' working portions, along with rule-of-thumb recommendations about promising research directions and suitable algorithms for practitioners in different fields.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Glove: Global Vectors for Word Representation
Pennington, J., Socher, R., & Manning, C. (2014) · Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.3115/v1/d14-1162 · Cited by 34,071
Nearest neighbor pattern classification
Cover, T., & Hart, P. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053964 · Cited by 16,936
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000
Item-based collaborative filtering recommendation algorithms
Sarwar, B., Karypis, G., Konstan, J., & Riedl, J. (2001) · Proceedings of the 10th international conference on World Wide Web · doi:10.1145/371920.372071 · Cited by 9,135
On the shortest spanning subtree of a graph and the traveling salesman problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1956-0078686-7 · Cited by 5,088
Voronoi diagrams—a survey of a fundamental geometric data structure
Aurenhammer, F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116880 · Cited by 4,340
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. (2020) · UTS ePRESS (University of Technology Sydney) · Cited by 3,174
Query by image and video content: the QBIC system
Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., et al. (1995) · Computer · doi:10.1109/2.410146 · Cited by 3,060
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
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
The small-world phenomenon: an algorithmic perspective
Kleinberg, J. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335325 · Cited by 1,882
Chávez, E., Navarro, G., Baeza-Yates, R., & Marroquín, J. L. (2001) · ACM Computing Surveys · doi:10.1145/502807.502808 · Cited by 1,246
Shamos, M. I., & Hoey, D. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.8 · Cited by 1,057
The relative neighbourhood graph of a finite planar set
Toussaint, G. T. (1980) · Pattern Recognition · doi:10.1016/0031-3203(80)90066-7 · Cited by 1,008
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
Similarity Search The Metric Space Approach
Zezula, P., Amato, G. M., Dohnal, V., & Batko, M. (2006) · The Kluwer international series on advances in database systems · doi:10.1007/0-387-29151-2 · Cited by 962
A weighted nearest neighbor algorithm for learning with symbolic features
Cost, S., & Salzberg, S. (1993) · Machine Learning · doi:10.1007/bf00993481 · Cited by 764
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
Subramanya, S. J., Devvrit, F., Simhadri, H. V., Krishnawamy, R., & Kadekodi, R. (2019) · neural information processing systems · Cited by 679
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
Relative neighborhood graphs and their relatives
Jaromczyk, J. W., & Toussaint, G. T. (1992) · Proceedings of the IEEE · doi:10.1109/5.163414 · Cited by 664
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
Navigability of complex networks
Boguñá, M., Krioukov, D., & Claffy, K. C. (2009) · Nature Physics · doi:10.1038/nphys1130 · Cited by 486
Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., & Lin, X. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2909204 · Cited by 454
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
Voronoi Diagrams and Delaunay Triangulations
Fortune, S. (2004) · Discrete mathematics and its applications · doi:10.1201/9781420035315.ch23 · Cited by 399
Optimized Product Quantization for Approximate Nearest Neighbor Search
Ge, T., He, K., Ke, Q., & Sun, J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.379 · Cited by 384
Fast approximate nearest neighbor search with the navigating spreading-out graph
Fu, C., Xiang, C., Wang, C., & Cai, D. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3303753.3303754 · Cited by 379
AnalyticDB-V: a hybrid analytical engine towards query fusion for structured and unstructured data
Wei, C., Wu, B., Wang, S., Lou, R., Zhan, C., Li, F., & Cai, Y. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3415478.3415541 · Cited by 251
Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection
Chen, J., Fang, H., & Saad, Y. (2008) · Cited by 236
FANNG: Fast Approximate Nearest Neighbour Graphs
Harwood, B., & Drummond, T. W. (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.616 · Cited by 222
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
ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms
Aumüller, M., Bernhardsson, E., & Faithfull, A. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-68474-1_3 · Cited by 198
SONG: Approximate Nearest Neighbor Search on GPU
Zhao, W., Tan, S., & Li, P. (2020) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde48307.2020.00094 · Cited by 197
Scalable 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 178
Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search
Muñoz, J. A. V., Gonçalves, M. A., Dias, Z., & Torres, R. D. S. (2019) · Pattern Recognition · doi:10.1016/j.patcog.2019.106970 · Cited by 137
Fu, C., Wang, C., & Cai, D. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3067706 · Cited by 126
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 113
Arora, A., Sinha, S., Kumar, P., & Bhattacharya, A. (2018) · Proceedings of the VLDB Endowment · doi:10.14778/3204028.3204034 · Cited by 109
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
Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination
Li, C., Zhang, M., Andersen, D. G., & He, Y. (2020) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3318464.3380600 · Cited by 107
Iwasaki, M., & Miyazaki, D. (2018) · arXiv (Cornell University) · doi:10.4230/lipics.sea.2020.1 · Cited by 105
Binary Hashing for Approximate Nearest Neighbor Search on Big Data: A Survey
Cao, Y., Qi, H., Zhou, W., Kato, J., Li, K., Liu, X., & Gui, J. (2017) · IEEE Access · doi:10.1109/access.2017.2781360 · Cited by 103
Molecular-level similarity search brings computing to DNA data storage
Bee, C., Chen, Y.-J., Queen, M., Ward, D., Liu, X., Organick, L., Seelig, G., Strauß, K., & Ceze, L. (2021) · Nature Communications · doi:10.1038/s41467-021-24991-z · Cited by 95
Trinary-Projection Trees for Approximate Nearest Neighbor Search
Wang, J., Wang, N., Jia, Y., Li, J., Zeng, G., Zha, H., & Hua, X. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.125 · Cited by 89
Query-driven iterated neighborhood graph search for large scale indexing
Wang, J., & Li, S. (2012) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/2393347.2393378 · Cited by 87
The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform
Li, J., Li, X., Gui, C., Chen, J., Ni, Z., Wang, N., & Chen, Y. (2018) · doi:10.1145/3284028.3284030 · Cited by 75
Using the k-Nearest Neighbor Graph for Proximity Searching in Metric Spaces
Paredes, R., & Chávez, E. (2005) · Lecture notes in computer science · doi:10.1007/11575832_14 · Cited by 74
Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces
Paredes, R., Chávez, E., Figueroa, K., & Navarro, G. (2006) · Lecture notes in computer science · doi:10.1007/11764298_8 · Cited by 70
Learning binary code for fast nearest subspace search
Zhou, L., Bai, X. P., Liu, X., Zhou, J. W., & Hancock, E. R. (2019) · Pattern Recognition · doi:10.1016/j.patcog.2019.107040 · Cited by 68
A survey on graph-based methods for similarity searches in metric spaces
Shimomura, L. C., Oyamada, R. S., Vieira, M. R., & Kaster, D. S. (2020) · Information Systems · doi:10.1016/j.is.2020.101507 · Cited by 63
Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?Preprint
Verma, N., Kpotufe, S., & Dasgupta, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1205.2609 · Cited by 60
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
VoroNet: A scalable object network based on Voronoi tessellations
Beaumont, O., Kermarrec, A.-M., Marchal, L., & Riviere, E. (2007) · 2007 IEEE International Parallel and Distributed Processing Symposium · doi:10.1109/ipdps.2007.370210 · Cited by 52
Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search
Boytsov, L., Novak, D., Malkov, Y., & Nyberg, E. (2016) · Proceedings of the 25th ACM International on Conference on Information and Knowledge Management · doi:10.1145/2983323.2983815 · Cited by 50
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
Link and Code: Fast Indexing with Graphs and Compact Regression Codes
Douze, M., Sablayrolles, A., & 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.00384 · Cited by 47
Product quantization with dual codebooks for approximate nearest neighbor search
Pan, Z., Wang, L., Wang, Y., & Liu, Y. (2020) · Neurocomputing · doi:10.1016/j.neucom.2020.03.016 · Cited by 40
Self-citationFast approximate similarity search based on degree-reduced neighborhood graphs
Aoyama, K., Saito, K., Sawada, H., & Ueda, N. (2011) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2020408.2020576 · Cited by 38
Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search
Iwasaki, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46759-7_2 · Cited by 37
Query-aware locality-sensitive hashing scheme for $$l_p$$ norm
Huang, Q., Feng, J., Fang, Q., Ng, W., & Wang, W. (2017) · The VLDB Journal · doi:10.1007/s00778-017-0472-7 · Cited by 37
iDEC: indexable distance estimating codes for approximate nearest neighbor search
Gong, L., Wang, H., Ogihara, M., & Xu, J. J. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3397230.3397243 · Cited by 37
Understanding and Improving Proximity Graph Based Maximum Inner Product Search
Liu, J., Yan, X., Dai, X., Li, Z., Cheng, J. S.-C., & Yang, M.-C. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i01.5344 · Cited by 33
Zhang, M., & He, Y. (2019) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3357384.3357938 · Cited by 32
Pyramid: A General Framework for Distributed Similarity Search on Large-scale Datasets
Deng, S., Yan, X., Ng, K. K. W., Jiang, C., & Cheng, J. S.-C. (2019) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata47090.2019.9006219 · Cited by 31
On Approximately Searching for Similar Word Embeddings
Sugawara, K., Kobayashi, H., & Iwasaki, M. (2016) · Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/p16-1214 · Cited by 28
Peer to Peer Multidimensional Overlays: Approximating Complex Structures
Beaumont, O., Kermarrec, A.-M., & Rivière, É. (2008) · Springer eBooks · doi:10.1007/978-3-540-77096-1_23 · Cited by 26
Kosuge, A., & Oshima, T. (2019) · IEEE International Conference on Graph Computing (GC) · doi:10.1109/gc46384.2019.00018 · Cited by 23
Being prepared in a sparse world: The case of KNN graph construction
Boutet, A., Kermarrec, A.-M., Mittal, N., & Taı̈ani, F. (2016) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2016.7498244 · Cited by 21
Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search
Ponomarenko, A., Avrelin, N., Naidan, B., et al. (2014) · Cited by 20
Fast Algorithm for Approximate k-Nearest Neighbor Graph Construction
Wang, D., Shi, L., & Cao, J. (2013) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2013.50 · Cited by 17
Multiattribute approximate nearest neighbor search based on navigable small world graph
Xu, X., Li, C., Wang, Y., & Xia, Y. (2020) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.5970 · Cited by 16
Self-citationTowards Similarity Graphs Constructed by Deep Reinforcement LearningPreprint
Baranchuk, D., & Babenko, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.12122 · Cited by 12
PMD: An Optimal Transportation-Based User Distance for Recommender Systems
Meng, Y., Dai, X., Yan, X., et al. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45442-5_34 · Cited by 12
Accelerating Large-Scale Molecular Similarity Search through Exploiting High Performance Computing
Zhu, C., Zhu, T., Li, H., Bi, J., & Song, M. (2019) · IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm47256.2019.8982950 · Cited by 12
Growing Homophilic Networks Are Natural Navigable Small Worlds
Malkov, Y. A., & Ponomarenko, A. (2016) · PLoS ONE · doi:10.1371/journal.pone.0158162 · Cited by 11
An Efficient Approximate kNN Graph Method for Diffusion on Image Retrieval
Magliani, F., McGuinness, K., Mohedano, E., & Prati, A. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-30645-8_49 · Cited by 10
Graph based Nearest Neighbor Search: Promises and FailuresPreprint
Lin, P.-C., & Zhao, W. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.02077 · Cited by 8
k-NN Graph Construction: a Generic Online Approach.Preprint
Zhao, W. (2018) · arXiv (Cornell University) · Cited by 4
HGraph: A Connected-Partition Approach to Proximity Graphs for Similarity Search
Shimomura, L. C., & Kaster, D. S. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-27615-7_8 · Cited by 4
Approximate k-NN Graph Construction: a Generic Online ApproachPreprint
Zhao, W., Wang, H., & Ngo, C. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1804.03032 · Cited by 3
Cited by
Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, P.-E., Lomeli, M., Hosseini, L., & Jégou, H. (2026) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2025.3618474 · Cited by 478
“This empirical complexity analysis has been used before for graph-based indices [73].”
Survey of Vector Database Management Systems
Pan, J. J., Wang, J., & Li, G. (2023) · arXiv · doi:10.48550/arxiv.2310.14021 · Cited by 184
Accelerating Retrieval-Augmented Generation
Quinn, D., Nouri, M., Patel, N., Salihu, J., Salemi, A., Lee, S., Zamani, H., & Alian, M. (2025) · Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 · doi:10.1145/3669940.3707264 · Cited by 48
GaussDB-Vector: A Large-Scale Persistent Real-Time Vector Database for LLM Applications
Sun, J., Li, G., Pan, J., Wang, J., Xie, Y., Liu, R., & Nie, W. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3750601.3750619 · Cited by 13
P-HNSW: Crash-Consistent HNSW for Vector Databases on Persistent Memory
Lee, H., Park, T., Na, Y., & Kim, W.-H. (2025) · Applied Sciences · doi:10.3390/app151910554 · Cited by 1
Metadata
- Authors
- Wang, M., Xu, X., Yue, Q., & Wang, Y.
- Venue
- Proceedings of the VLDB Endowment
- Published
- 2021-07
- Volume
- 14
- Issue
- 11
- Pages
- 1964-1978
- ISSN
- 2150-8097 (ISSN-L)
- OpenAlex
- W3128793550
- Cited by
- 264
- References
- 81
- FWCI
- 8.73
- Type
- journal article
- Language
- en
- Open access
- green
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.