DBScholar

Back to papers

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
h8e9a15bb0d33fb80
Venue
VLDB
Year
2025
Pagerank
4.9793485e-05
Overall Rank
11,449 | 23.03%
DOI
10.14778/3712221.3712241

Incoming Non-self Citations Over Time

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

Authors

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
Previous Page 1 / 1 Next

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.0012092602
22 Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud 2012 VLDB 0.00055962491
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
1,340 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00010973645
1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.9953879e-05
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,920 Effective Caching of Shortest Paths for Location-Based Services 2012 SIGMOD 6.9252611e-05
4,488 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.5781787e-05
5,300 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 6.1896851e-05
5,730 Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints 2021 SIGMOD 6.0154682e-05
6,107 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 5.8852347e-05
6,408 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.7942038e-05
6,988 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6274541e-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
7,716 Accelerating Exact Constrained Shortest Paths on GPUs 2021 VLDB 5.4683652e-05
8,393 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3410533e-05
9,166 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.2148514e-05
9,543 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1614165e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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