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

Approximate nearest neighbor search (ANNS) constitutes an important operation\nin a multitude of applications, including recommendation systems, information\nretrieval, and pattern recognition. In the past decade, graph-based ANNS\nalgorithms have been the leading paradigm in this domain, with dozens of\ngraph-based ANNS algorithms proposed. Such algorithms aim to provide effective,\nefficient solutions for retrieving the nearest neighbors for a given query.\nNevertheless, these efforts focus on developing and optimizing algorithms with\ndifferent approaches, so there is a real need for a comprehensive survey about\nthe approaches' relative performance, strengths, and pitfalls. Thus here we\nprovide a thorough comparative analysis and experimental evaluation of 13\nrepresentative graph-based ANNS algorithms via a new taxonomy and fine-grained\npipeline. We compared each algorithm in a uniform test environment on eight\nreal-world datasets and 12 synthetic datasets with varying sizes and\ncharacteristics. Our study yields novel discoveries, offerings several useful\nprinciples to improve algorithms, thus designing an optimized method that\noutperforms the state-of-the-art algorithms. This effort also helped us\npinpoint algorithms' working portions, along with rule-of-thumb recommendations\nabout promising research directions and suitable algorithms for practitioners\nin different fields.\n