Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks

Summary: Architecture-Intact oracle for dynamic spatial networks using randomization. Delivers fast distance and shortest-path queries with negligible updates; preprocessing/space O(n log^2 n), distance query O(log^4 n log log n) and path O(log^4 n log log n + l); updates O(log^3 n) w.h.p. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5995
Venue: SIGMOD
Year: 2020
Pagerank: 6.5083151e-05
Overall Rank: 4,786 | 67.17%
DOI: 10.1145/3318464.3389718

Incoming Non-self Citations Over Time

Authors

1. Victor Junqiu Wei (Huawei)
2. Raymond Chi-Wing Wong (Hong Kong University of Science and Technology)
3. Cheng Long (Nanyang Technological University)

BibTeX Citation

@inproceedings{wei_sigmod20,
        title = {{Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks}},
        author = {Wei, Victor Junqiu and Wong, Raymond Chi-Wing and Long, Cheng},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389718},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389718},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
9,553	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	5.2528121e-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
9,891	GTX: A Write-Optimized Latch-free Graph Data System with Transactional Support	2025	SIGMOD	5.1997534e-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,845	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	5.093636e-05
11,695	Towards Crowd-aware Indoor Path Planning	2021	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
449	Query Processing in Spatial Network Databases	2003	VLDB	0.0001826404
949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013028107
968	Path Oracles for Spatial Networks	2009	VLDB	0.00012901559
1,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011664469
1,232	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011566372
1,598	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010242826
1,613	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010216983
1,745	Querying Shortest Paths on Time Dependent Road Networks	2019	VLDB	9.861709e-05
4,498	Constrained Shortest Path Query in a Large Time-Dependent Graph	2019	VLDB	6.6613027e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,226	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB
2	7,211	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB
3	9,619	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD
4	11,156	Proximity Queries on Point Clouds using Rapid Construction Path Oracle	2024	SIGMOD
5	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
6	433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD
7	11,993	Distance Oracle on Terrain Surface	2017	SIGMOD
8	1,205	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD
9	949	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
10	968	Path Oracles for Spatial Networks	2009	VLDB