DBScholar

Back to papers

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

Summary: Revisits RNG/NSWG construction to expose superlinear bottlenecks and introduces a pruning-based edge-selection framework. Accelerates index building by up to 5.6× while preserving or improving k-ANN search quality. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h59ac501b2388bdbf
Venue
VLDB
Year
2025
Pagerank
6.8040917e-05
Overall Rank
4,077 | 72.68%
DOI
10.14778/3725688.3725709
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{yang_vldb25,
        title = {{Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search}},
        author = {Yang, Shuo and Xie, Jiadong and Liu, Yingfan and Yu, Jeffrey Xu and Gao, Xiyue and Wang, Qianru and Peng, Yanguo and Cui, Jiangtao},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {6},
        pages = {1825--1838},
        doi = {10.14778/3725688.3725709},
        url = {https://doi.org/10.14778/3725688.3725709},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank Citing Paper Year Venue Pagerank
5,903 MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search 2025 SIGMOD 5.9357915e-05
7,610 Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.4683985e-05
7,719 VSAG: An Optimized Search Framework for Graph-based Approximate Nearest Neighbor Search 2025 VLDB 5.4543461e-05
8,281 Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study 2026 SIGMOD 5.3462537e-05
8,434 Fast Approximate Similarity Join in Vector Databases 2025 SIGMOD 5.3165535e-05
10,358 WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search 2026 SIGMOD 5.0156513e-05
10,359 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 5.0156513e-05
10,588 Through the Lens of Hubness: A Revisit on Graph-Based Approximate Nearest Neighbor Search: [Experiments & Analysis] 2026 SIGMOD 4.9605343e-05
10,623 Beyond Vector Search: Querying With and Without Predicates 2026 SIGMOD 4.9605343e-05
10,707 Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph 2026 SIGMOD 4.9605343e-05
10,714 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD 4.9605343e-05
10,768 SVFusion: A CPU-GPU Co-Processing Architecture for Large-Scale Real-Time Vector Search 2026 VLDB 4.9605343e-05
10,797 I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration 2026 VLDB 4.9605343e-05
10,898 Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization 2026 VLDB 4.9605343e-05
10,907 HEXA: A Disjoint-Subgraph-Based Indexing Framework for Approximate Nearest Neighbor Search at Billion Scale 2026 VLDB 4.9605343e-05
10,921 GAS: A Lightweight Framework for Filtered Search over Wide-table Vectors 2026 VLDB 4.9605343e-05
11,098 Advances of Query Processing in Vector Databases 2026 VLDB 4.9605343e-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
75 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037163157
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
181 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00026425782
281 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022262975
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
286 Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search 2016 VLDB 0.00022090962
335 A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search 2021 VLDB 0.0002067515
339 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020558018
562 SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index 2015 VLDB 0.00016344855
578 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016079505
837 Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination 2020 SIGMOD 0.00013530806
925 SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search 2014 VLDB 0.00013026835
1,165 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD 0.00011708765
1,610 Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment 2024 SIGMOD 0.00010066881
1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.00010045437
1,968 SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search 2024 SIGMOD 9.2810141e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,117 Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts 2025 VLDB
2 10,473 Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation 2026 PODS
3 10,714 FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search 2026 SIGMOD
4 10,637 Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph 2026 SIGMOD
5 1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB
6 75 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB
7 1,165 Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases 2023 SIGMOD
8 10,900 RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search 2026 VLDB
9 10,898 Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization 2026 VLDB
10 10,359 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD