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.00012620373
Overall Rank: 993 | 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
954	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00012856563
1,233	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011397529
1,250	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011325987
1,430	On k-skip Shortest Paths	2011	SIGMOD	0.00010676829
1,577	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010155939
1,581	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010151896
1,653	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9588776e-05
3,676	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	7.0882436e-05
4,631	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.4784075e-05
5,893	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.9394451e-05
7,008	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.6061911e-05
7,031	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	5.6000241e-05
7,922	Origin-Destination Travel Time Oracle for Map-based Services	2023	SIGMOD	5.4092668e-05
9,347	Processing Proximity Relations in Road Networks	2010	SIGMOD	5.176541e-05
10,601	Efficient Proximity Queries on Simplified Height Maps	2026	SIGMOD	4.9605343e-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
449	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018112854
463	Query Processing in Spatial Network Databases	2003	VLDB	0.00017806376
681	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00014792999
1,053	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00012260546
2,206	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	8.850101e-05

Semantically Similar Papers

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