An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network

Summary: Defines a complete DSP space by determinant/constraint dimensions and benchmarks state-of-the-art methods under synthetic network setup. Introduces dynamic degree to classify environments and uses throughput as a guideline metric, validated on real networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h94ea731a8c914ce8
Venue: VLDB
Year: 2021
Pagerank: 5.6274541e-05
Overall Rank: 6,988 | 53.02%
DOI: 10.14778/3476249.3476267

Incoming Non-self Citations Over Time

Authors

1. Mengxuan Zhang (University of Queensland)
2. Lei Li (University of Queensland)
3. Xiaofang Zhou (Hong Kong University of Science and Technology)

BibTeX Citation

@article{zhang_vldb21,
        title = {{An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network}},
        author = {Zhang, Mengxuan and Li, Lei and Zhou, Xiaofang},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {11},
        pages = {2127--2140},
        doi = {10.14778/3476249.3476267},
        url = {https://doi.org/10.14778/3476249.3476267},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,906	Diversified Top-k Route Planning in Road Network	2022	VLDB	6.3616468e-05
9,543	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	5.1614165e-05
10,003	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	5.0979044e-05
11,263	Continuous Lifelong Conflict-Aware AGV Routing with Kinematic Constraints	2025	VLDB	4.9793485e-05
11,449	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	4.9793485e-05
11,752	TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks	2023	VLDB	4.9793485e-05

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
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
447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018159715
953	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00012877507
990	Path Oracles for Spatial Networks	2009	VLDB	0.00012648672
1,232	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.0001141008
1,252	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011336944
1,340	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00010973645
1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010163696
1,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.9953879e-05
1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9875545e-05
1,722	Querying Shortest Paths on Time Dependent Road Networks	2019	VLDB	9.7932895e-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
3,497	Anytime Stochastic Routing with Hybrid Learning	2020	VLDB	7.2556245e-05
3,920	Effective Caching of Shortest Paths for Location-Based Services	2012	SIGMOD	6.9252611e-05
4,175	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	6.757832e-05
4,633	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.4933316e-05
4,634	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.4933103e-05
4,783	Distributed Processing of k Shortest Path Queries over Dynamic Road Networks	2020	SIGMOD	6.4159993e-05
7,351	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB	5.5449734e-05
9,166	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.2148514e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,407	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB
2	9,240	Shortest Paths Discovery in Uncertain Networks via Transfer Learning	2023	SIGMOD
3	5,336	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
4	1,722	Querying Shortest Paths on Time Dependent Road Networks	2019	VLDB
5	5,951	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB
6	953	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
7	4,604	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB
8	4,340	Constrained Shortest Path Query in a Large Time-Dependent Graph	2019	VLDB
9	2,141	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB
10	4,783	Distributed Processing of k Shortest Path Queries over Dynamic Road Networks	2020	SIGMOD