A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search
2021 · Mengzhao Wang, Xiaoliang Xu, Qiang Yue, et al.
Abstract
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 characteri
Authors
(none)
Tags
Stats
Related papers
- Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
- A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
- A Revisit Of Hashing Algorithms For Approximate Nearest Neighbor Search (2016)11.19
- Parlayann: Scalable And Deterministic Parallel Graph-based Approximate Nearest Neighbor Search Algorithms (2023)10.35
- Understanding And Generalizing Monotonic Proximity Graphs For Approximate Nearest Neighbor Search (2021)0.00
- CAGRA: Highly Parallel Graph Construction And Approximate Nearest Neighbor Search For Gpus (2023)12.17
- EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
- Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search Algorithms On Edge Devices (2024)0.00