Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts

Summary: SHG accelerates hierarchical ANN search by skipping redundant intermediate levels via shortcuts that safely determine navigation jumps, combined with hierarchical vector compression. It delivers 1.5–1.8× speedups and up to 20% higher recall over state-of-the-art indexes. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h2baae47ee773d676
Venue: VLDB
Year: 2025
Pagerank: 5.0830849e-05
Overall Rank: 10,078 | 32.25%
DOI: 10.14778/3748191.3748212

Incoming Non-self Citations Over Time

Authors

1. Zengyang Gong (Hong Kong University of Science and Technology)
2. Yuxiang Zeng (Beihang University)
3. Lei Chen (FYTRI; Hong Kong University of Science and Technology)

BibTeX Citation

@article{gong_vldb25,
        title = {{Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts}},
        author = {Gong, Zengyang and Zeng, Yuxiang and Chen, Lei},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {10},
        pages = {3518--3530},
        doi = {10.14778/3748191.3748212},
        url = {https://doi.org/10.14778/3748191.3748212},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,509	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor Search	2026	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021833987
341	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00020539791
345	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00020445545
463	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017804544
868	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013354403
1,625	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	0.0001004502
1,684	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	9.8801753e-05
2,085	SingleStore-V: An Integrated Vector Database System in SingleStore	2024	VLDB	9.0709364e-05
3,697	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.0882335e-05
5,527	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0936219e-05
9,700	Experimental Analysis of Large-scale Learnable Vector Storage Compression	2024	VLDB	5.1381949e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,642	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD
2	5,886	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD
3	7,004	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD
4	1,684	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB
5	4,050	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB
6	10,326	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
7	74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB
8	10,563	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD
9	1,170	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
10	1,625	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB