2021

A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search

Wang, Mengzhao, Xu, Xiaoliang, Yue, Qiang et al.

Understand

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.

Built on

On the shortest spanning subtree of a graph and the traveling salesman problem
Joseph B Kruskal. 1956 · 1956
Earlier work this paper cites.
Nearest neighbor pattern classification
Thomas Cover and Peter Hart. 1967 · 1967
Earlier work this paper cites.
Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) . IEEE, 151–162
Michael Ian Shamos and Dan Hoey. 1975 · 1975
Earlier work this paper cites.
The relative neighbourhood graph of a finite planar set
Godfried T Toussaint. 1980 · 1980
Earlier work this paper cites.
Voronoi diagrams—a survey of a fundamental geometric data structure
Franz Aurenhammer. 1991 · 1991
Earlier work this paper cites.
Constructing the relative neighborhood graph in 3-dimensional Euclidean space
Jerzy W Jaromczyk and Mirosław Kowaluk. 1991 · 1991
Earlier work this paper cites.
Relative neighborhood graphs and their relatives
Jerzy W Jaromczyk and Godfried T Toussaint. 1992 · 1992
Earlier work this paper cites.
A weighted nearest neighbor algorithm for learning with symbolic features
Scott Cost and Steven Salzberg. 1993 · 1993
Earlier work this paper cites.
Query by image and video content: The QBIC system
Myron Flickner, Harpreet Sawhney, Wayne Niblack, Jonathan Ashley, Qian Huang, Byron Dom, Monika Gorkani, Jim Hafner, Denis Lee, Dragutin Petkovic, et al · 1995
Earlier work this paper cites.
Voronoi diagrams and Delaunay triangulations
Steven Fortune. 1995 · 1995
Earlier work this paper cites.
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. 1998 · 1998
Earlier work this paper cites.
A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB , Vol. 98. 194–205
Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998 · 1998
Earlier work this paper cites.
The small-world phenomenon: An algorithmic perspective. In Proceedings of the thirty-second annual ACM symposium on Theory of computing . 163–170
Jon Kleinberg. 2000 · 2000
Earlier work this paper cites.
Searching in metric spaces
Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, and José Luis Marroquín. 2001 · 2001
Earlier work this paper cites.
Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web . 285–295
Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001 · 2001
Earlier work this paper cites.
Proximity graphs for nearest neighbor decision rules: recent progress. In Progress”, Proceedings of the 34 th Symposium on the INTERFACE . Citeseer
Godfried Toussaint. 2002 · 2002
Earlier work this paper cites.
Divide-and-conquer algorithm for creating neighborhood graph for clustering. In Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004. , Vol. 1. IEEE, 264–267
Olli Virmajoki and Pasi Franti. 2004 · 2004
Earlier work this paper cites.
Using the k-nearest neighbor graph for proximity searching in metric spaces. In International Symposium on String Processing and Information Retrieval . Springer, 127–138
Rodrigo Paredes and Edgar Chávez. 2005 · 2005
Earlier work this paper cites.
Practical construction of k-nearest neighbor graphs in metric spaces. In International Workshop on Experimental and Efficient Algorithms . Springer, 85–97
Rodrigo Paredes, Edgar Chávez, Karina Figueroa, and Gonzalo Navarro. 2006 · 2006
Earlier work this paper cites.
Similarity search: the metric space approach . Vol. 32
Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. 2006 · 2006
Earlier work this paper cites.
VoroNet: A scalable object network based on Voronoi tessellations. In 2007 IEEE International Parallel and Distributed Processing Symposium . IEEE, 1–10
Olivier Beaumont, Anne-Marie Kermarrec, Loris Marchal, and Étienne Rivière. 2007b · 2007
Earlier work this paper cites.
Optimised KD-trees for fast image descriptor matching. In 2008 IEEE Conference on Computer Vision and Pattern Recognition . IEEE, 1–8
Chanop Silpa-Anan and Richard Hartley. 2008 · 2008
Earlier work this paper cites.
Navigability of complex networks
Marian Boguna, Dmitri Krioukov, and Kimberly C Claffy. 2009 · 2009
Earlier work this paper cites.
Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection
Jie Chen, Haw-ren Fang, and Yousef Saad. 2009 · 2009
Earlier work this paper cites.
Efficient construction of neighborhood graphs by the multiple sorting method
Original
Takeaki Uno, Masashi Sugiyama, and Koji Tsuda. 2009 · 2009
Earlier work this paper cites.
Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?. In UAI 2009, Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, Montreal, QC, Canada, June 18-21, 2009 . 565–574
Nakul Verma, Samory Kpotufe, and Sanjoy Dasgupta. 2009 · 2009
Earlier work this paper cites.
Neighborhood graphs for indexing and retrieving multi-dimensional data
Hakim Hacid and Tetsuya Yoshida. 2010 · 2010
Earlier work this paper cites.
Product quantization for nearest neighbor search
Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010 · 2010
Earlier work this paper cites.
Literature survey on nearest neighbor search and search in graphs
Philipp M Riegger. 2010 · 2010
Earlier work this paper cites.
Fast approximate similarity search based on degree-reduced neighborhood graphs. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining . 1055–1063
Kazuo Aoyama, Kazumi Saito, Hiroshi Sawada, and Naonori Ueda. 2011 · 2011
Earlier work this paper cites.
Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web . 577–586
Wei Dong, Charikar Moses, and Kai Li. 2011 · 2011
Earlier work this paper cites.
Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Twenty-Second International Joint Conference on Artificial Intelligence
Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011 · 2011
Earlier work this paper cites.
Proximity graphs: E, δ \delta , Δ \Delta , χ \chi and ω \omega
Prosenjit Bose, Vida Dujmović, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Vera Sacristán, Maria Saumell, and David R Wood. 2012 · 2012
Earlier work this paper cites.
Query-driven iterated neighborhood graph search for large scale indexing. In Proceedings of the 20th ACM international conference on Multimedia . 179–188
Jingdong Wang and Shipeng Li. 2012 · 2012
Earlier work this paper cites.
Scalable k-nn graph construction for visual descriptors. In 2012 IEEE Conference on Computer Vision and Pattern Recognition . IEEE, 1106–1113
Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, and Shipeng Li. 2012 · 2012
Earlier work this paper cites.
Graph index based query-by-example search on a large speech data set. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing . IEEE, 8520–8524
Kazuo Aoyama, Atsunori Ogawa, Takashi Hattori, Takaaki Hori, and Atsushi Nakamura. 2013 · 2013
Earlier work this paper cites.
Optimized Product Quantization for Approximate Nearest Neighbor Search. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, June 23-28, 2013 . IEEE Computer Society, 2946–2953
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013 · 2013
Earlier work this paper cites.
Fast algorithm for approximate k-nearest neighbor graph construction. In 2013 IEEE 13th international conference on data mining workshops . IEEE, 349–356
Dilin Wang, Lei Shi, and Jianwen Cao. 2013a · 2013
Earlier work this paper cites.
Trinary-projection trees for approximate nearest neighbor search
Jingdong Wang, Naiyan Wang, You Jia, Jian Li, Gang Zeng, Hongbin Zha, and Xian-Sheng Hua. 2013b · 2013
Earlier work this paper cites.

Similar

Fast kNN graph construction with locality sensitive hashing. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases . Springer, 660–674
Yan-Ming Zhang, Kaizhu Huang, Guanggang Geng, and Cheng-Lin Liu. 2013 · 2013
Cited alongside, same era.
Large scale nearest neighbors search based on neighborhood graph. In 2013 International Conference on Advanced Cloud and Big Data . IEEE, 181–186
Wenhui Zhou, Chunfeng Yuan, Rong Gu, and Yihua Huang. 2013 · 2013
Cited alongside, same era.
Fast and accurate hashing via iterative nearest neighbors expansion
Zhongming Jin, Debing Zhang, Yao Hu, Shiding Lin, Deng Cai, and Xiaofei He. 2014 · 2014
Cited alongside, same era.
Approximate nearest neighbor algorithm based on navigable small world graphs
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014 · 2014
Cited alongside, same era.
Comparative analysis of data structures for approximate nearest neighbor search
Alexander Ponomarenko, Nikita Avrelin, Bilegsaikhan Naidan, and Leonid Boytsov. 2014 · 2014
Cited alongside, same era.
Query-aware locality-sensitive hashing for approximate nearest neighbor search
Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015 · 2015
Cited alongside, same era.
Permutation Search Methods are Efficient, Yet Faster Search is Possible
Bilegsaikhan Naidan, Leonid Boytsov, and Eric Nyberg. 2015 · 2015
Cited alongside, same era.
Very Deep Convolutional Networks for Large-Scale Image Recognition. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings
Karen Simonyan and Andrew Zisserman. 2015 · 2015
Cited alongside, same era.
Learning to hash for indexing big data—A survey
Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. 2015 · 2015
Cited alongside, same era.
Being prepared in a sparse world: the case of KNN graph construction. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE) . IEEE, 241–252
Antoine Boutet, Anne-Marie Kermarrec, Nupur Mittal, and François Taïani. 2016 · 2016
Cited alongside, same era.
Off the beaten path: Let’s replace term-based retrieval with k-nn search. In Proceedings of the 25th ACM international on conference on information and knowledge management . 1099–1108
Leonid Boytsov, David Novak, Yury Malkov, and Eric Nyberg. 2016 · 2016
Cited alongside, same era.
Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph
Original
Cong Fu and Deng Cai. 2016 · 2016
Cited alongside, same era.

Then

An Efficient Approximate kNN Graph Method for Diffusion on Image Retrieval. In International Conference on Image Analysis and Processing . Springer, 537–548
Federico Magliani, Kevin McGuinness, Eva Mohedano, and Andrea Prati. 2019 · 2019
Later among the works it cites.
An Introduction to Proximity Graphs
Luke Mathieson and Pablo Moscato. 2019 · 2019
Later among the works it cites.
Hierarchical clustering-based graphs for large scale approximate nearest neighbor search
Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres. 2019 · 2019
Later among the works it cites.
HGraph: A Connected-Partition Approach to Proximity Graphs for Similarity Search. In International Conference on Database and Expert Systems Applications . Springer, 106–121
Larissa Capobianco Shimomura and Daniel S Kaster. 2019 · 2019
Later among the works it cites.
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS 2019 . 1771–13781
Suhas Jayaram Subramanya, F Devvrit, HV Simhadri, R Krishnawamy, and R Kadekodi. 2019 · 2019
Later among the works it cites.
A Genetic Programming Approach for Searching on Nearest Neighbors Graphs. In Proceedings of the 2019 on International Conference on Multimedia Retrieval . 43–47
Javier A Vargas Muñoz, Zanoni Dias, and Ricardo da S. Torres. 2019 · 2019
Later among the works it cites.
GRIP: Multi-Store Capacity-Optimized High-Performance Nearest Neighbor Search for Vector Search Engine. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management . 1673–1682
Minjia Zhang and Yuxiong He. 2019 · 2019
Later among the works it cites.
Learning to Anneal and Prune Proximity Graphs for Similarity Search
Minjia Zhang, Wenhan Wang, and Yuxiong He. 2019 · 2019
Later among the works it cites.
On the Merge of k-NN Graph
Original
Wan-Lei Zhao, Peng-Cheng Lin, and Chong-Wah Ngo. 2019a · 2019
Later among the works it cites.
Accelerating Large-Scale Molecular Similarity Search through Exploiting High Performance Computing. In 2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM) . IEEE, 330–333
Chun Jiang Zhu, Tan Zhu, Haining Li, Jinbo Bi, and Minghu Song. 2019 · 2019
Later among the works it cites.
Datasets for approximate nearest neighbor search
Anon. 2010 · 2020
Later among the works it cites.
Million Song Dataset Benchmarks
Anon. 2011 · 2020
Later among the works it cites.
Common Crawl
Anon. unknowna · 2020
Later among the works it cites.
TIMIT Audio
Anon. unknownb · 2020
Later among the works it cites.
Content-Based Similarity Search in Large-Scale DNA Data Storage Systems
Callista Bee, Yuan-Jyue Chen, David Ward, Xiaomeng Liu, Georg Seelig, Karin Strauss, and Luis H Ceze. 2020 · 2020
Later among the works it cites.
Benchmarking nearest neighbors
Erik Bernhardsson. 2017 · 2020
Later among the works it cites.
KGraph: A Library for Approximate Nearest Neighbor Search
Wei Dong. 2011 · 2020
Later among the works it cites.
iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search
Long Gong, Huayi Wang, Mitsunori Ogihara, and Jun Xu. 2020 · 2020
Later among the works it cites.
Neighborhood Graph and Tree for Indexing High-dimensional Data
Masajiro Iwasaki. 2015 · 2020
Later among the works it cites.
GloVe: Global Vectors for Word Representation
Pennington Jeffrey, Socher Richard, and D. Manning Christopher. 2015 · 2020
Later among the works it cites.
HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogeneous Memory. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020)
Jie Ren, Minjia Zhang, and Dong Li. 2020 · 2020
Later among the works it cites.
FAISS: Facebook AI Similarity Search
Jeff Johnson, Matthijs Douze, Hervé Jégou, and Hosseini Lucas. 2017 · 2020
Later among the works it cites.
Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data . 2539–2554
Conglong Li, Minjia Zhang, David G Andersen, and Yuxiong He. 2020 · 2020
Later among the works it cites.
Understanding and Improving Proximity Graph Based Maximum Inner Product Search. In Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 34. 139–146
Jie Liu, Xiao Yan, Xinyan Dai, Zhirong Li, James Cheng, and Ming-Chang Yang. 2020 · 2020
Later among the works it cites.
PMD: An Optimal Transportation-Based User Distance for Recommender Systems. In European Conference on Information Retrieval . Springer, 272–280
Yitong Meng, Xinyan Dai, Xiao Yan, James Cheng, Weiwen Liu, Jun Guo, Benben Liao, and Guangyong Chen. 2020 · 2020
Later among the works it cites.
An Open Source Vector Similarity Search Engine
Milvus. 2019 · 2020
Later among the works it cites.
Product quantization with dual codebooks for approximate nearest neighbor search
Zhibin Pan, Liangzhuang Wang, Yang Wang, and Yuchen Liu. 2020 · 2020
Later among the works it cites.
Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning . PMLR, 7803–7813
Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020 · 2020
Later among the works it cites.
Enron Email Dataset
Stewart Russell, Manning Christopher, and Pennington Jeffrey. 2015 · 2020
Later among the works it cites.
A survey on graph-based methods for similarity searches in metric spaces
Larissa C Shimomura, Rafael Seidi Oyamada, Marcos R Vieira, and Daniel S Kaster. 2020 · 2020
Later among the works it cites.
AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data
Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020 · 2020
Later among the works it cites.
A comprehensive survey on graph neural networks
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020 · 2020
Later among the works it cites.
Multiattribute approximate nearest neighbor search based on navigable small world graph
Xiaoliang Xu, Chang Li, Yuxiang Wang, and Yixing Xia. 2020 · 2020
Later among the works it cites.
SONG: Approximate Nearest Neighbor Search on GPU. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) . IEEE, 1033–1044
Weijie Zhao, Shulong Tan, and Ping Li. 2020 · 2020
Later among the works it cites.
Learning binary code for fast nearest subspace search
Lei Zhou, Xiao Bai, Xianglong Liu, Jun Zhou, and Edwin R Hancock. 2020 · 2020
Later among the works it cites.
High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility
Cong Fu, Changxu Wang, and Deng Cai. 2021 · 2021
Closest in time.
A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs
Eric S Tellez, Guillermo Ruiz, Edgar Chavez, and Mario Graff. 2021 · 2021
Closest in time.
Binary hashing for approximate nearest neighbor search on big data: A survey
Yuan Cao, Heng Qi, Wenrui Zhou, Jien Kato, Keqiu Li, Xiulong Liu, and Jie Gui. 2017 · 2054
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…