Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks

Summary: Proposes Dual-Hierarchy Labelling (DHL) for dynamic road networks, using two complementary hierarchies (query and update) to enable selective label exploration for fast distance queries. Dynamic maintenance and a parallel variant deliver faster construction/update; 2–4× faster queries and 10–20% labeling on ten large networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7032
Venue: SIGMOD
Year: 2025
Pagerank: 4.3341665e-05
Overall Rank: 9,470 | 34.12%
DOI: 10.1145/3709685

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,075	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.1945683e-05
10,669	Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,170	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013511856
1,690	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010904736
2,201	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.3048105e-05
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5683079e-05
3,342	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.197276e-05
4,193	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	6.37019e-05
5,250	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	5.6044961e-05
6,594	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD	4.999751e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5683079e-05
10,874	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	4.1945683e-05
1,230	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00013150837
10,669	Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks	2025	VLDB	4.1945683e-05
3,342	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.197276e-05
7,444	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	4.7281454e-05
1,690	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010904736
1,378	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012294512
2,201	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.3048105e-05
6,594	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD	4.999751e-05