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

arXiv: https://arxiv.org/abs/1707.00143 · HTML: https://mlsanity.com/paper/1707.00143/

## Key facts

- Cited by 104 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2017.

## Built on by (most cited first, 30 of 104)

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [RAGCache: Efficient Knowledge Caching for Retrieval-Augmented Generation](https://mlsanity.com/paper/2404.12457/) (2024)
- [PQCache: Product Quantization-based KVCache for Long Context LLM Inference](https://mlsanity.com/paper/2407.12820/) (2024)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models](https://mlsanity.com/paper/2310.09949/) (2023)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Similarity search in the blink of an eye with compressed indices](https://mlsanity.com/paper/2304.04759/) (2023)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [RAGO: Systematic Performance Optimization for Retrieval-Augmented Generation Serving](https://mlsanity.com/paper/2503.14649/) (2025)
- [Uni-Retriever: Towards Learning The Unified Embedding Based Retriever in Bing Sponsored Search](https://mlsanity.com/paper/2202.06212/) (2022)
- [OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries](https://mlsanity.com/paper/2211.12850/) (2022)
- [Visual and Object Geo-localization: A Comprehensive Survey](https://mlsanity.com/paper/2112.15202/) (2021)
- [RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference](https://mlsanity.com/paper/2505.02922/) (2025)
- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [Locally-Adaptive Quantization for Streaming Vector Search](https://mlsanity.com/paper/2402.02044/) (2024)
- [Inference-time sparse attention with asymmetric indexing](https://mlsanity.com/paper/2502.08246/) (2025)
- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [TransHash: Transformer-based Hamming Hashing for Efficient Image Retrieval](https://mlsanity.com/paper/2105.01823/) (2021)
- [ESPN: Memory-Efficient Multi-Vector Information Retrieval](https://mlsanity.com/paper/2312.05417/) (2023)
- [A Hybrid RAG System with Comprehensive Enhancement on Complex Reasoning](https://mlsanity.com/paper/2408.05141/) (2024)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Progressively Optimized Bi-Granular Document Representation for Scalable Embedding Based Retrieval](https://mlsanity.com/paper/2201.05409/) (2022)
- [Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints](https://mlsanity.com/paper/2203.13601/) (2022)
- [Flashlight: Scalable Link Prediction with Effective Decoders](https://mlsanity.com/paper/2209.10100/) (2022)
- [Automating Nearest Neighbor Search Configuration with Constrained Optimization](https://mlsanity.com/paper/2301.01702/) (2023)
- [Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits](https://mlsanity.com/paper/2405.18680/) (2024)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [TOD: GPU-accelerated Outlier Detection via Tensor Operations](https://mlsanity.com/paper/2110.14007/) (2021)
- [Binary Embedding-based Retrieval at Tencent](https://mlsanity.com/paper/2302.08714/) (2023)

## Abstract (arXiv)

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 search scenario of Taobao (Alibaba Group) and has been integrated into their search engine at billion-node scale.