A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks

Summary: G2H is a CPU-GPU hybrid hop-labeling method for rapidly rebuilding road-network distance indexes under frequent updates, combining hybrid graph partitioning, optimized ordering, and parallel label pruning. It constructs indexes for 6M-vertex networks in under a minute and serves hundreds of millions of queries per second. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14423
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 11,097 | 23.87%
DOI: 10.14778/3712221.3712241

Incoming Non-self Citations Over Time

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

Authors

1. Jiajia Li (Shenyang Aerospace University)
2. Yongzhi Chen (Shenyang Aerospace University)
3. Mengxuan Zhang (Australian National University)
4. Lei Li (Hong Kong University of Science and Technology)

BibTeX Citation

@article{li_vldb25,
        title = {{A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks}},
        author = {Li, Jiajia and Chen, Yongzhi and Zhang, Mengxuan and Li, Lei},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {3},
        pages = {770--783},
        doi = {10.14778/3712221.3712241},
        url = {https://doi.org/10.14778/3712221.3712241},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
20	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056944564
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010216983
2,097	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	9.1725037e-05
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
2,871	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	8.0110616e-05
3,834	Effective Caching of Shortest Paths for Location-Based Services	2012	SIGMOD	7.0841464e-05
4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.7229209e-05
5,250	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	6.2992176e-05
5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	6.1508076e-05
5,987	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	6.0183678e-05
6,292	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD	5.9251728e-05
6,844	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.7566172e-05
7,158	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	5.6858492e-05
7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.6667372e-05
7,573	Accelerating Exact Constrained Shortest Paths on GPUs	2021	VLDB	5.5938767e-05
9,003	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.3345443e-05
9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3201316e-05
9,364	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	5.2798829e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,460	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
2	10,788	Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks	2025	SIGMOD
3	1,232	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD
4	1,251	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB
5	11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
6	7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
7	6,292	Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks	2023	SIGMOD
8	2,871	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD
9	9,619	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
10	1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD