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: 9901
Venue: VLDB
Year: 2009
Pagerank: 0.00015137526
Overall Rank: 945 | 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,054	On k-skip Shortest Paths	2011	SIGMOD	0.00014422699
1,170	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013511856
1,378	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012294512
1,690	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010904736
1,823	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010413508
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881
2,201	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.3048105e-05
4,193	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	6.37019e-05
5,250	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	5.6044961e-05
6,138	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1915368e-05
6,494	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.0417258e-05
7,277	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	4.7794907e-05
8,284	Origin-Destination Travel Time Oracle for Map-based Services	2023	SIGMOD	4.5435639e-05
8,986	Processing Proximity Relations in Road Networks	2010	SIGMOD	4.4153655e-05
10,016	Efficient Proximity Queries on Simplified Height Maps	2026	SIGMOD	4.1945683e-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
389	Query Processing in Spatial Network Databases	2003	VLDB	0.00024620268
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023310419
598	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019474545
983	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00014860126
1,526	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	0.00011512916

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,376	Succinct Graph Representations as Distance Oracles: An Experimental Evaluation	2022	VLDB	4.1945683e-05
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
1,054	On k-skip Shortest Paths	2011	SIGMOD	0.00014422699
7,236	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB	4.7932355e-05
1,690	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010904736
10,938	Proximity Queries on Point Clouds using Rapid Construction Path Oracle	2024	SIGMOD	4.1945683e-05
11,789	Distance Oracle on Terrain Surface	2017	SIGMOD	4.1945683e-05
1,170	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013511856
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00023310419
5,250	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	5.6044961e-05