Path Oracles for Spatial Networks

Summary: Introduces linear-size path oracles compressing all n² spatial-network shortest paths into relational tuples via spatial coherence and WSPs. B-tree lookups retrieve path links in O(log n), with an ε-approximate distance/vertex variant for scalable SQL routing. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h6fa5ef0d83da8af3
Venue: VLDB
Year: 2009
Pagerank: 0.00012642908
Overall Rank: 991 | 93.35%
DOI: 10.14778/1687627.1687763

Incoming Non-self Citations Over Time

Authors

1. Jagan Sankaranarayanan (University of Maryland)
2. Hanan Samet (University of Maryland)
3. Houman Alborzi (Google; University of Maryland)

BibTeX Citation

@article{sankaranarayanan_vldb09,
        title = {{Path Oracles for Spatial Networks}},
        author = {Sankaranarayanan, Jagan and Samet, Hanan and Alborzi, Houman},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687763},
        url = {https://doi.org/10.14778/1687627.1687763},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
953	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00012871412
1,234	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011404678
1,253	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011331798
1,426	On k-skip Shortest Paths	2011	SIGMOD	0.00010705427
1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010158887
1,645	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.9906562e-05
1,647	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9828268e-05
3,689	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0921741e-05
4,636	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.4902578e-05
5,897	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.952769e-05
6,991	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6247902e-05
7,053	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.6103309e-05
7,906	Origin-Destination Travel Time Oracle for Map-based Services	2023	SIGMOD	5.4272125e-05
9,322	Processing Proximity Relations in Road Networks	2010	SIGMOD	5.1937083e-05
10,535	Efficient Proximity Queries on Simplified Height Maps	2026	SIGMOD	4.9769913e-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
447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018151383
459	Query Processing in Spatial Network Databases	2003	VLDB	0.00017860573
678	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00014836541
1,048	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00012297664
2,196	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	8.8763791e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,280	Succinct Graph Representations as Distance Oracles: An Experimental Evaluation	2022	VLDB
2	355	On Graph Query Optimization in Large Networks	2010	VLDB
3	1,426	On k-skip Shortest Paths	2011	SIGMOD
4	7,354	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB
5	1,234	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD
6	11,509	Proximity Queries on Point Clouds using Rapid Construction Path Oracle	2024	SIGMOD
7	12,297	Distance Oracle on Terrain Surface	2017	SIGMOD
8	447	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD
9	953	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB
10	4,636	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD