Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph

By Cong Fu, Chao Xiang, Changxu Wang, Deng Cai. Proceedings of the VLDB Endowment, 2017

560 citations recorded by the source corpus.

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 Graph (MRNG) which guarantees very low search complexity (close to logarithmic time). To further lower the indexing complexity and make it practical for billion-node ANNS problems, we propose a novel graph structure named Navigating Spreading-out Graph (NSG) by approximating the MRNG. The NSG takes the four aspects into account simultaneously. Extensive experiments show that NSG outperforms all the existing algorithms significantly. In addition, NSG shows superior performance in the E-commercial scenario of Taobao (Alibaba Group) and has been integrated into their billion-scale search engine.

Subfields: Computer Vision and Pattern Recognition, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/8843bdc4548bd2f9b483aafe90b7ee41c8b8fdc8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

1. Hai Jin
2. Qiang Yue
3. Yuxiang Wang
4. Mengzhao Wang
5. Xiaoliang Xu

In Signal Processing

1. Hai Jin
2. Qiang Yue
3. Yuxiang Wang
4. Mengzhao Wang
5. Xiaoliang Xu

Citations in the corpus

• The Faiss Library (2024, unknown): “In this example, we index 1.5 trillion vectors in 144 dimensions.”
• Milvus: A Purpose-Built Vector Data Management System (2021, background): “InMilvus, wemainly support two types of indexes:3 quantizationbased indexes (including IVF_FLAT [3, 33, 35], IVF_SQ8 [3, 35], and IVF_PQ [3, 22, 33, 35]) and graph-based indexes (including HNSW [49] and RNSG [20]) to serve different applications.”
• A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, methodology): “The problem of graph-based ANNS on high-dimensional and largescale data has been studied intensively across the literature [38].”
• VIBE: Vector Index Benchmark for Embeddings (2025, unknown): “For results on all algorithms, see our companion website or Appendix F.2 for results on two datasets.”
• MINT: Multi-Vector Search Index Tuning (2025, unknown): “Graph-based techniques organize items in graphs and are prevalent these days because of their efficiency and high recall [5, 6, 29–31, 55, 56].”