Path Oracles for Spatial Networks

Summary: Path oracle encodes all-pairs shortest paths in a spatial network as a single path tuple, enabling SP queries with SQL. Uses WSP-based grouping for O(s^d n) with O(log n) lookups; adds a path-distance oracle for eps distances; shows scaling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9902
Venue: VLDB
Year: 2009
Pagerank: 0.00015117675
Overall Rank: 946 | 93.43%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,052	On k-skip Shortest Paths	2011	SIGMOD	0.00014403922
1,173	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013501079
1,385	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012259478
1,694	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010870205
1,822	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010404349
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277
2,206	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.2958349e-05
4,194	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	6.3640644e-05
5,255	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	5.5991117e-05
6,144	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1865526e-05
6,491	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.0368875e-05
7,271	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	4.7764555e-05
8,278	Origin-Destination Travel Time Oracle for Map-based Services	2023	SIGMOD	4.5392079e-05
8,992	Processing Proximity Relations in Road Networks	2010	SIGMOD	4.4111332e-05
10,016	Efficient Proximity Queries on Simplified Height Maps	2026	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
391	Query Processing in Spatial Network Databases	2003	VLDB	0.00024560891
434	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023277433
597	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019450818
985	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00014834799
1,545	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	0.00011428609

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,378	Succinct Graph Representations as Distance Oracles: An Experimental Evaluation	2022	VLDB	4.1905499e-05
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261
1,052	On k-skip Shortest Paths	2011	SIGMOD	0.00014403922
7,240	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB	4.7869144e-05
1,694	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010870205
10,941	Proximity Queries on Point Clouds using Rapid Construction Path Oracle	2024	SIGMOD	4.1905499e-05
11,797	Distance Oracle on Terrain Surface	2017	SIGMOD	4.1905499e-05
434	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023277433
1,173	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013501079
5,255	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	5.5991117e-05