DBScholar

Back to papers

Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees

Summary: Maintains Contraction Hierarchies under streaming and batch road-network updates via a shortcut-centric SS-Graph and weight propagation, avoiding broad index reconstruction. Provides theoretical guarantees and 2–3 orders-of-magnitude faster streaming maintenance than prior work. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
12448
Venue
VLDB
Year
2020
Pagerank
9.1725037e-05
Overall Rank
2,097 | 85.62%
DOI
10.14778/3377369.3377371

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{ouyang_vldb20,
        title = {{Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees}},
        author = {Ouyang, Dian and Yuan, Long and Qin, Lu and Chang, Lijun and Zhang, Ying and Lin, Xuemin},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {5},
        pages = {602--615},
        doi = {10.14778/3377369.3377371},
        url = {https://doi.org/10.14778/3377369.3377371},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
2,871 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 8.0110616e-05
3,612 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.2579119e-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,418 Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale 2022 VLDB 5.6236086e-05
8,525 QARTA: An ML-based System for Accurate Map Services 2021 VLDB 5.4119882e-05
9,229 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 5.3017894e-05
9,619 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.2434488e-05
9,815 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 5.214913e-05
10,366 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 5.093636e-05
10,788 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 5.093636e-05
10,789 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 5.093636e-05
10,860 Continuous Lifelong Conflict-Aware AGV Routing with Kinematic Constraints 2025 VLDB 5.093636e-05
10,918 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025 VLDB 5.093636e-05
11,097 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 5.093636e-05
11,248 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 5.093636e-05
11,452 Automatic Road Extraction with Multi-Source Data Revisited: Completeness, Smoothness and Discrimination 2023 VLDB 5.093636e-05
11,710 A Demonstration of QARTA: An ML-based System for Accurate Map Services 2021 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Previous Page 1 / 1 Next

Semantically Similar Papers