DBScholar

Back to papers

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

Summary: Introduces MRNG, a low-degree monotonic graph with near-logarithmic ANNS search. Its practical approximation, NSG, jointly preserves connectivity, short paths, and compact indexing, enabling billion-scale deployment and outperforming prior graph methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
12167
Venue
VLDB
Year
2019
Pagerank
0.00034701237
Overall Rank
93 | 99.37%
DOI
10.14778/3303753.3303754

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{fu_vldb19,
        title = {{Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph}},
        author = {Fu, Cong and Xiang, Chao and Wang, Changxu and Cai, Deng},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {5},
        pages = {461--474},
        doi = {10.14778/3303753.3303754},
        url = {https://doi.org/10.14778/3303753.3303754},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 124 citing papers.

Rank Citing Paper Year Venue Pagerank
286 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00022357911
398 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.00019194947
406 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00019054532
926 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00013181732
1,065 PASE: PostgreSQL Ultra-High-Dimensional Approximate Nearest Neighbor Search Extension 2020 SIGMOD 0.00012335063
1,244 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD 0.00011508159
1,357 RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search 2024 SIGMOD 0.00011043994
1,515 ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data 2024 SIGMOD 0.00010521317
1,589 Manu: A Cloud Native Vector Database Management System 2022 VLDB 0.00010264469
1,735 High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations 2023 SIGMOD 9.9004924e-05
1,760 Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment 2024 SIGMOD 9.8157819e-05
1,802 HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search 2022 VLDB 9.7284341e-05
1,934 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 9.4561907e-05
2,010 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 9.3085202e-05
2,303 SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search 2024 SIGMOD 8.7783079e-05
2,519 Similarity search in the blink of an eye with compressed indices 2023 VLDB 8.4741476e-05
2,534 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 8.4561875e-05
2,572 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4027322e-05
2,734 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.190416e-05
2,920 SingleStore-V: An Integrated Vector Database System in SingleStore 2024 VLDB 7.9628307e-05
3,108 Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search 2025 SIGMOD 7.7499741e-05
3,240 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.6071649e-05
3,279 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.5711218e-05
3,286 iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search 2024 SIGMOD 7.5596483e-05
3,310 Similarity Query Processing for High-Dimensional Data 2020 VLDB 7.5363562e-05
3,335 Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search 2024 SIGMOD 7.5098031e-05
3,364 Vexless: A Serverless Vector Data Management System Using Cloud Functions 2024 SIGMOD 7.4796687e-05
3,799 SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search 2025 SIGMOD 7.114484e-05
4,116 RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search 2024 VLDB 6.892012e-05
4,430 PQCache: Product Quantization-based KVCache for Long Context LLM Inference 2025 SIGMOD 6.7091071e-05
4,712 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 6.5506649e-05
5,653 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 6.1332953e-05
5,800 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 6.0850924e-05
6,133 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 5.9654376e-05
6,148 Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes 2024 VLDB 5.9593368e-05
6,334 MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search 2025 SIGMOD 5.9093559e-05
6,404 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.8859287e-05
6,432 RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference 2026 VLDB 5.8801533e-05
6,615 A Topology-Aware Localized Update Strategy for Graph-Based ANN Index 2026 VLDB 5.8214312e-05
6,650 Tribase: A Vector Data Query Engine for Reliable and Lossless Pruning Compression using Triangle Inequalities 2025 SIGMOD 5.8146324e-05
6,691 Dumpy: A Compact and Adaptive Index for Large Data Series Collections 2023 SIGMOD 5.8011086e-05
6,765 AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models 2025 SIGMOD 5.7808599e-05
6,820 DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter 2025 SIGMOD 5.7632132e-05
6,851 Maximum Inner Product is Query-Scaled Nearest Neighbor 2025 VLDB 5.7546877e-05
6,995 Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models 2025 VLDB 5.7301567e-05
7,124 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 5.6961208e-05
7,145 Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search 2025 SIGMOD 5.6908957e-05
7,166 Accelerating Graph Indexing for ANNS on Modern CPUs 2025 SIGMOD 5.6846045e-05
7,259 Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search 2025 SIGMOD 5.6613405e-05
7,426 Dynamic Range-Filtering Approximate Nearest Neighbor Search 2025 VLDB 5.6211019e-05
Previous Page 1 / 3 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
21 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00056760516
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
221 Robust and Fast Similarity Search for Moving Object Trajectories 2005 SIGMOD 0.00024224879
332 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00020920444
705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014829964
805 Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan 2016 VLDB 0.00013891999
990 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00012796562
1,572 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.00010329197
1,628 Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs 2014 SIGMOD 0.00010186757
2,673 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 8.2730112e-05
3,363 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 7.4808966e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,832 Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search 2025 VLDB
2 10,455 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD
3 1,934 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB
4 10,362 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 2026 SIGMOD
5 9,892 Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts 2025 VLDB
6 10,364 Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph 2026 SIGMOD
7 4,712 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB
8 10,454 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD
9 398 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB
10 1,244 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD