Querying Shortest Paths on Time Dependent Road Networks

Summary: Proposes TD-G-tree, a height-balanced index for time-dependent road networks. Indexing only border TDSPs with hierarchical partitions enables fast TDSP queries and time-interval routing via DP and chronological divide-and-conquer; real-data experiments show gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hffb90b56822947a0
Venue: VLDB
Year: 2019
Pagerank: 9.7867948e-05
Overall Rank: 1,717 | 88.50%
DOI: 10.14778/3342263.3342265
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Yong Wang (Tsinghua University)
2. Guoliang Li (Tsinghua University)
3. Nan Tang (Hamad Bin Khalifa University; Qatar Computing Research Institute)

BibTeX Citation

@article{wang_vldb19,
        title = {{Querying Shortest Paths on Time Dependent Road Networks}},
        author = {Wang, Yong and Li, Guoliang and Tang, Nan},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {11},
        pages = {1249--1261},
        doi = {10.14778/3342263.3342265},
        url = {https://doi.org/10.14778/3342263.3342265},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,150	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.9509559e-05
2,794	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.987154e-05
3,123	RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s	2021	SIGMOD	7.6082482e-05
4,631	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.4784075e-05
6,720	A Deep Generative Model for Trajectory Modeling and Utilization	2023	VLDB	5.6839455e-05
7,008	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6061911e-05
8,197	Nuhuo: An Effective Estimation Model for Traffic Speed Histogram Imputation on A Road Network	2024	VLDB	5.3635777e-05
8,563	Hunting Temporal Bumps in Graphs with Dynamic Vertex Properties	2022	SIGMOD	5.3002237e-05
8,721	QARTA: An ML-based System for Accurate Map Services	2021	VLDB	5.2705676e-05
9,679	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD	5.1258854e-05
9,956	Efficient Stochastic Routing in Path-Centric Uncertain Road Networks	2024	VLDB	5.0910746e-05
10,043	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	5.0786422e-05
10,685	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	2026	SIGMOD	4.9605343e-05
11,095	Are We There Yet? A Grand Tour of ETA Queries	2026	VLDB	4.9605343e-05
11,192	Bursting Flow Query on Large Temporal Flow Networks	2025	SIGMOD	4.9605343e-05
12,050	Towards Crowd-aware Indoor Path Planning	2021	VLDB	4.9605343e-05
12,064	A Demonstration of QARTA: An ML-based System for Accurate Map Services	2021	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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,624	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010028661
4,190	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	6.7361423e-05
13,969	R3: A Real-Time Route Recommendation System	2014	VLDB	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,695	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
2	10,638	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD
3	4,931	Diversified Top-k Route Planning in Road Network	2022	VLDB
4	5,357	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
5	1,270	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB
6	1,581	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
7	2,150	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB
8	1,233	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD
9	7,399	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
10	9,679	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD