Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph
2017 · Cong Fu, Chao Xiang, Changxu Wang, et al.
Abstract
Approximate nearest neighbor search (ANNS) is a fundamental problem in databases and data mining. A scalable ANNS algorithm should be both memory-efficient and fast. Some early graph-based approaches have shown attractive theoretical guarantees on search time complexity, but they all suffer from the problem of high indexing time complexity. Recently, some graph-based methods have been proposed to reduce indexing complexity by approximating the traditional graphs; these methods have achieved revolutionary performance on million-scale datasets. Yet, they still can not scale to billion-node databases. In this paper, to further improve the search-efficiency and scalability of graph-based methods, we start by introducing four aspects: (1) ensuring the connectivity of the graph; (2) lowering the average out-degree of the graph for fast traversal; (3) shortening the search path; and (4) reducing the index size. Then, we propose a novel graph structure called Monotonic Relative Neighborhood Gr
Authors
(none)
Tags
Stats
Related papers
- High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30
- A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35
- Relative Nn-descent: A Fast Index Construction For Graph-based Approximate Nearest Neighbor Search (2023)8.09
- EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
- Theoretical And Empirical Analysis Of Adaptive Entry Point Selection For Graph-based Approximate Nearest Neighbor Search (2024)0.00
- Parlayann: Scalable And Deterministic Parallel Graph-based Approximate Nearest Neighbor Search Algorithms (2023)10.35
- BAMG: A Block-aware Monotonic Graph Index For Disk-based Approximate Nearest Neighbor Search (2025)0.00
- Sparse Neighborhood Graph-based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis And Optimization (2025)0.00