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: 14167
Venue: VLDB
Year: 2025
Pagerank: 5.1997534e-05
Overall Rank: 9,892 | 32.14%
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,297	TaCo: Data-adaptive and Query-aware Subspace Collision for High-dimensional Approximate Nearest Neighbor Search	2026	SIGMOD	5.093636e-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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020920444
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
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
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,920	SingleStore-V: An Integrated Vector Database System in SingleStore	2024	VLDB	7.9628307e-05
3,792	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	7.1220982e-05
5,800	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.0850924e-05
9,520	Experimental Analysis of Large-scale Learnable Vector Storage Compression	2024	VLDB	5.2561283e-05

Semantically Similar Papers

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