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

Summary: SHG: hierarchical-graph ANN index combining hierarchical vector compression with a novel “shortcuts” structure that computes safe skip counts to bypass redundant intermediate levels and cut distance computations. Delivers 1.5–1.8× speedup and up to 20% recall gain vs. SOTA. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13979
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,683 | 25.69%
DOI: 10.14778/3748191.3748212

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752
736	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00017447617
770	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016917602
857	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00015882892
1,478	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00011762542
2,725	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.2294908e-05
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
3,680	SingleStore-V: An Integrated Vector Database System in SingleStore	2024	VLDB	6.8496415e-05
5,074	Learned Index: A Comprehensive Experimental Evaluation	2023	VLDB	5.7175726e-05
6,376	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0916875e-05
9,408	Experimental Analysis of Large-scale Learnable Vector Storage Compression	2024	VLDB	4.3441378e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,166	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
8,245	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	4.5514956e-05
8,439	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	4.5128946e-05
2,725	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.2294908e-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
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.1945683e-05
2,023	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.7544991e-05
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05