DBScholar

Back to papers

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
10092
Venue
VLDB
Year
2009
Pagerank
0.00012901559
Overall Rank
968 | 93.37%
DOI
10.14778/1687627.1687763

Incoming Non-self Citations Over Time

Authors

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
949 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013028107
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,386 On k-skip Shortest Paths 2011 SIGMOD 0.00010950754
1,553 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.0001037809
1,613 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 0.00010216983
1,622 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010201102
3,612 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.2579119e-05
4,786 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.5083151e-05
5,784 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 6.0896788e-05
6,844 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.7566172e-05
6,940 Exact Top-k Nearest Keyword Search in Large Networks 2015 SIGMOD 5.7331991e-05
8,516 Origin-Destination Travel Time Oracle for Map-based Services 2023 SIGMOD 5.4119882e-05
9,143 Processing Proximity Relations in Road Networks 2010 SIGMOD 5.3153925e-05
10,314 Efficient Proximity Queries on Simplified Height Maps 2026 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

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
433 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018532516
449 Query Processing in Spatial Network Databases 2003 VLDB 0.0001826404
665 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00015167291
1,025 An Efficient and Scalable Approach to CNN Queries in a Road Network 2005 VLDB 0.00012578515
2,153 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 9.0762376e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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