Database Paper Browser

Back to papers

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

Summary: Introduces MRNG (Monotonic Relative Neighborhood Graph) with near-logarithmic ANNS search, and NSG (Navigating Spreading-out Graph) as a scalable MRNG-based approximation; focuses on connectivity, low out-degree, short search paths, and compact indexing. Empirical results on million- to billion-scale data show NSG beating baselines and deployed in Alibaba Taobao’s billion-scale search engine. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
11979
Venue
VLDB
Year
2019
Pagerank
0.00033913475
Overall Rank
212 | 98.53%
DOI
10.14778/3303753.3303754

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 113 citing papers.

Rank Citing Paper Year Venue Pagerank
8,439 Accelerating Graph Indexing for ANNS on Modern CPUs 2025 SIGMOD 4.5128946e-05
8,485 Maximum Inner Product is Query-Scaled Nearest Neighbor 2025 VLDB 4.4999394e-05
8,497 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 4.4981377e-05
8,656 Dynamic Range-Filtering Approximate Nearest Neighbor Search 2025 VLDB 4.4737647e-05
8,712 ANN Softmax: Acceleration of Extreme Classification Training 2022 VLDB 4.4626362e-05
8,899 Fast Approximate Similarity Join in Vector Databases 2025 SIGMOD 4.427232e-05
9,103 AlayaDB: The Data Foundation for Efficient and Effective Long-context LLM Inference 2025 SIGMOD 4.3958197e-05
9,283 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 4.3631652e-05
9,291 DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search 2026 SIGMOD 4.3619549e-05
9,394 BigVectorBench: Heterogeneous Data Embedding and Compound Queries are Essential in Evaluating Vector Databases 2025 VLDB 4.3441378e-05
9,480 Cost-Effective, Low Latency Vector Search with Azure Cosmos DB 2025 VLDB 4.3341665e-05
9,552 Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs 2025 SIGMOD 4.3254416e-05
9,822 DIDS: Double Indices and Double Summarizations for Fast Similarity Search 2024 VLDB 4.2757088e-05
9,879 HARMONY: A Scalable Distributed Vector Database for High-Throughput Approximate Nearest Neighbor Search 2026 SIGMOD 4.2643674e-05
9,880 CoTra: Towards Efficient and Scalable Distributed Vector Search with RDMA 2026 SIGMOD 4.2643674e-05
9,881 VStream: A Distributed Streaming Vector Search System 2025 VLDB 4.2643674e-05
9,914 RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search 2025 SIGMOD 4.2561557e-05
10,007 Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation 2026 PODS 4.1945683e-05
10,031 PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs 2026 SIGMOD 4.1945683e-05
10,039 VecFlow: A High-Performance Vector Data Management System for Filtered-Search on GPUs 2026 SIGMOD 4.1945683e-05
10,042 Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations 2026 SIGMOD 4.1945683e-05
10,052 Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study 2026 SIGMOD 4.1945683e-05
10,054 Beyond Vector Search: Querying With and Without Predicates 2026 SIGMOD 4.1945683e-05
10,071 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
10,073 Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph 2026 SIGMOD 4.1945683e-05
10,086 High-Throughput, Cost-Effective Billion-Scale Vector Search with a Single GPU 2026 SIGMOD 4.1945683e-05
10,095 NeurStore: Efficient In-database Deep Learning Model Management System 2026 SIGMOD 4.1945683e-05
10,110 SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation 2026 SIGMOD 4.1945683e-05
10,111 Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
10,124 TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning 2026 SIGMOD 4.1945683e-05
10,129 WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
10,141 Honeybee: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning 2026 SIGMOD 4.1945683e-05
10,150 Curator: Efficient Vector Search with Low-Selectivity Filters 2026 SIGMOD 4.1945683e-05
10,154 Distribution-Aware Exploration for Adaptive HNSW Search 2026 SIGMOD 4.1945683e-05
10,158 Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph 2026 SIGMOD 4.1945683e-05
10,160 Efficient Vector Index Merging in Vector Databases 2026 SIGMOD 4.1945683e-05
10,165 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
10,166 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
10,201 RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search 2026 SIGMOD 4.1945683e-05
10,204 Reveal Hidden Pitfalls and Navigate Next Generation of Vector Similarity Search from Task-Centric Views: [Experiments & Analysis] 2026 SIGMOD 4.1945683e-05
10,222 RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference 2026 VLDB 4.1945683e-05
10,224 SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search 2026 VLDB 4.1945683e-05
10,237 Quantization Meets Projection: A Happy Marriage for Approximate k-Nearest Neighbor Search 2026 VLDB 4.1945683e-05
10,256 I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration 2026 VLDB 4.1945683e-05
10,260 JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search 2026 VLDB 4.1945683e-05
10,273 An Experimental Evaluation of Hybrid Querying on Vectors 2026 VLDB 4.1945683e-05
10,287 RED-ANNS: An RDMA-Enabled Distributed Framework for Graph-Based Approximate Nearest Neighbor Search 2026 VLDB 4.1945683e-05
10,303 Elastic Index Selection for Label-Hybrid AKNN Search 2026 VLDB 4.1945683e-05
10,409 MicroNN: An On-device Disk-resident Updatable Vector Database 2025 SIGMOD 4.1945683e-05
10,566 Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search 2025 VLDB 4.1945683e-05
Previous Page 2 / 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
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
34 Similarity Search in High Dimensions via Hashing 1999 VLDB 0.00076637636
79 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056242144
251 Robust and Fast Similarity Search for Moving Object Trajectories 2005 SIGMOD 0.00030644658
562 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00020091752
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
1,229 SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013157271
1,269 Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan 2016 VLDB 0.00012930432
1,920 Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs 2014 SIGMOD 0.00010090791
1,971 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 9.893198e-05
3,056 DSH: Data Sensitive Hashing for High-Dimensional k-NN Search 2014 SIGMOD 7.6432146e-05
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
10,566 Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search 2025 VLDB 4.1945683e-05
10,166 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
2,971 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7970531e-05
10,071 Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
10,683 Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts 2025 VLDB 4.1945683e-05
10,073 Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph 2026 SIGMOD 4.1945683e-05
5,569 Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search 2025 VLDB 5.4290942e-05
10,165 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1945683e-05
770 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.00016917602
2,023 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD 9.7544991e-05