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.7886535e-05
Overall Rank: 1,724 | 88.42%
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,143	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.9625587e-05
2,944	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.8277412e-05
3,115	RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s	2021	SIGMOD	7.6315625e-05
4,636	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.4902578e-05
6,705	A Deep Generative Model for Trajectory Modeling and Utilization	2023	VLDB	5.7028025e-05
6,991	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6247902e-05
8,181	Nuhuo: An Effective Estimation Model for Traffic Speed Histogram Imputation on A Road Network	2024	VLDB	5.3813718e-05
8,545	Hunting Temporal Bumps in Graphs with Dynamic Vertex Properties	2022	SIGMOD	5.3178076e-05
8,701	QARTA: An ML-based System for Accurate Map Services	2021	VLDB	5.2880532e-05
9,921	Efficient Stochastic Routing in Path-Centric Uncertain Road Networks	2024	VLDB	5.1079647e-05
10,008	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	5.0954911e-05
10,587	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD	4.9769913e-05
10,624	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	2026	SIGMOD	4.9769913e-05
11,034	Are We There Yet? A Grand Tour of ETA Queries	2026	VLDB	4.9769913e-05
11,132	Bursting Flow Query on Large Temporal Flow Networks	2025	SIGMOD	4.9769913e-05
12,006	Towards Crowd-aware Indoor Path Planning	2021	VLDB	4.9769913e-05
12,020	A Demonstration of QARTA: An ML-based System for Accurate Map Services	2021	VLDB	4.9769913e-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,622	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010049301
4,175	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	6.7546329e-05
13,929	R3: A Real-Time Route Recommendation System	2014	VLDB	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,806	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
2	10,575	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD
3	4,907	Diversified Top-k Route Planning in Road Network	2022	VLDB
4	5,343	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,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD
7	2,143	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB
8	1,234	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD
9	7,379	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
10	10,587	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD