Database Paper Browser

Back to papers

Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search

Summary: Diagnoses superlinear construction bottlenecks in proximity-graph (RNG, NSWG) indexes for k-ANN at scale. Introduces a pruning-based edge-selection construction framework (applied to RNG and integrated into NSWG) that cuts build time up to 5.6× while preserving k-ANN effectiveness. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
13841
Venue
VLDB
Year
2025
Pagerank
5.423881e-05
Overall Rank
5,577 | 61.25%
DOI
10.14778/3725688.3725709

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank Citing Paper Year Venue Pagerank
8,208 VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search 2025 VLDB 4.5537353e-05
8,239 MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search 2025 SIGMOD 4.5471319e-05
8,899 Fast Approximate Similarity Join in Vector Databases 2025 SIGMOD 4.4229886e-05
10,052 Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study 2026 SIGMOD 4.1905499e-05
10,054 Beyond Vector Search: Querying With and Without Predicates 2026 SIGMOD 4.1905499e-05
10,111 Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
10,129 WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
10,158 Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph 2026 SIGMOD 4.1905499e-05
10,165 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
10,166 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
10,224 SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search 2026 VLDB 4.1905499e-05
10,256 I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration 2026 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank Cited Paper Year Venue Pagerank
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
210 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00034086264
301 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028396714
399 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00024359304
494 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00021769407
579 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.0001982328
596 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00019455943
675 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00018304179
763 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.00016963981
858 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00015833075
1,225 SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013182109
1,347 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00012463441
2,002 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD 9.8258191e-05
2,692 Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment 2024 SIGMOD 8.2857267e-05
2,969 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7955562e-05
3,552 SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search 2024 SIGMOD 6.9765275e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,239 MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search 2025 SIGMOD 4.5471319e-05
763 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.00016963981
10,691 Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts 2025 VLDB 4.1905499e-05
10,006 Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation 2026 PODS 4.1905499e-05
10,166 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
10,073 Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph 2026 SIGMOD 4.1905499e-05
2,969 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7955562e-05
210 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00034086264
2,002 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD 9.8258191e-05
10,165 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05