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.7932895e-05
Overall Rank: 1,722 | 88.43%
DOI: 10.14778/3342263.3342265

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,141	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.9668034e-05
2,943	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	7.8314485e-05
3,113	RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s	2021	SIGMOD	7.6351769e-05
4,633	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.4933316e-05
6,701	A Deep Generative Model for Trajectory Modeling and Utilization	2023	VLDB	5.7055034e-05
6,988	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6274541e-05
8,175	Nuhuo: An Effective Estimation Model for Traffic Speed Histogram Imputation on A Road Network	2024	VLDB	5.3839205e-05
8,538	Hunting Temporal Bumps in Graphs with Dynamic Vertex Properties	2022	SIGMOD	5.3203262e-05
8,693	QARTA: An ML-based System for Accurate Map Services	2021	VLDB	5.2905577e-05
9,914	Efficient Stochastic Routing in Path-Centric Uncertain Road Networks	2024	VLDB	5.1103839e-05
10,003	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	5.0979044e-05
10,576	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD	4.9793485e-05
10,613	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	2026	SIGMOD	4.9793485e-05
11,025	Are We There Yet? A Grand Tour of ETA Queries	2026	VLDB	4.9793485e-05
11,123	Bursting Flow Query on Large Temporal Flow Networks	2025	SIGMOD	4.9793485e-05
12,000	Towards Crowd-aware Indoor Path Planning	2021	VLDB	4.9793485e-05
12,014	A Demonstration of QARTA: An ML-based System for Accurate Map Services	2021	VLDB	4.9793485e-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,621	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010054061
4,175	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	6.757832e-05
13,924	R3: A Real-Time Route Recommendation System	2014	VLDB	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,799	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
2	10,564	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD
3	4,906	Diversified Top-k Route Planning in Road Network	2022	VLDB
4	5,336	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
5	1,269	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,141	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB
8	1,232	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD
9	7,377	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
10	10,576	Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks	2026	SIGMOD