An Experimental Study on Hub Labeling based Shortest Path Algorithms

Summary: Comprehensive study of hub-labeling shortest-path indexes, benchmarking state-of-the-art methods against alternatives for efficiency and applicability. Introduces Significant-path-based Hub Pushing (SHP), reducing index construction time while retaining fast queries. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hac7ececd674d0dec
Venue: VLDB
Year: 2018
Pagerank: 0.00010973645
Overall Rank: 1,340 | 91.00%
DOI: 10.1145/3164135.3164141

Incoming Non-self Citations Over Time

Authors

1. Ye Li (University of Macau)
2. Leong Hou U (University of Macau)
3. Man Lung Yiu (Hong Kong Polytechnic University)
4. Ngai Meng Kou (University of Macau)

BibTeX Citation

@article{li_vldb18,
        title = {{An Experimental Study on Hub Labeling based Shortest Path Algorithms}},
        author = {Li, Ye and U, Leong Hou and Yiu, Man Lung and Kou, Ngai Meng},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {4},
        pages = {445--457},
        doi = {10.1145/3164135.3164141},
        url = {https://doi.org/10.1145/3164135.3164141},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,141	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.9668034e-05
2,188	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8874739e-05
2,943	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.8314485e-05
3,687	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0955331e-05
5,000	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3202341e-05
5,703	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.0303375e-05
5,803	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	5.9893561e-05
6,177	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.8598586e-05
6,988	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6274541e-05
7,229	The Simpler The Better: An Indexing Approach for Shared-Route Planning Queries	2020	VLDB	5.5797235e-05
7,302	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.5602499e-05
7,377	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.5395908e-05
9,166	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.2148514e-05
9,407	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB	5.1828314e-05
9,809	Fast Network K-function-based Spatial Analysis	2022	VLDB	5.1257999e-05
10,004	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.0979044e-05
10,274	Succinct Graph Representations as Distance Oracles: An Experimental Evaluation	2022	VLDB	5.0485061e-05
11,205	Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks	2025	SIGMOD	4.9793485e-05
11,251	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.9793485e-05
11,449	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	4.9793485e-05
11,551	LION: Fast and High-Resolution Network Kernel Density Visualization	2024	VLDB	4.9793485e-05
11,580	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.9793485e-05
11,752	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.9793485e-05
11,775	Approximating Probabilistic Group Steiner Trees in Graphs	2023	VLDB	4.9793485e-05
12,002	Fast Augmentation Algorithms for Network Kernel Density Visualization	2021	VLDB	4.9793485e-05
12,032	SpeakNav: Voice-based Route Description Language Understanding for Template-driven Path Search	2021	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025584127
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019485934
953	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00012877507
1,232	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.0001141008
1,252	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011336944
1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010163696
1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9875545e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,408	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD
2	9,166	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB
3	1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
4	1,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
5	7,377	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
6	1,252	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD
7	9,799	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
8	5,803	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB
9	11,580	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
10	5,703	Hub Labeling for Shortest Path Counting	2020	SIGMOD