Database Paper Browser

Back to papers

Scalable Network Distance Browsing in Spatial Databases

Summary: Best-first kNN on spatial networks with precomputed all-pairs shortest paths and a first-edge decomposition, decoupling path work from candidate sets. Shortest-path quadtree uses spatial coherence to trim storage from O(N^3) to O(N^1.5) and lets the same paths be reused across object queries when the network is static. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3977
Venue
SIGMOD
Year
2008
Pagerank
0.00023277433
Overall Rank
434 | 96.99%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank Citing Paper Year Venue Pagerank
946 Path Oracles for Spatial Networks 2009 VLDB 0.00015117675
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,511 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00011582099
1,545 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 0.00011428609
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
3,949 Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets 2012 VLDB 6.5929931e-05
4,136 Effective Caching of Shortest Paths for Location-Based Services 2012 SIGMOD 6.4131651e-05
4,194 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 6.3640644e-05
4,739 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD 5.9515822e-05
4,856 TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks 2018 VLDB 5.868876e-05
4,896 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 5.8467149e-05
5,255 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 5.5991117e-05
6,203 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB 5.1552752e-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
7,313 Nearest Keyword Search in XML Documents 2011 SIGMOD 4.7599924e-05
7,382 Shortest Path Computation with No Information Leakage 2012 VLDB 4.740535e-05
7,897 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 4.6186066e-05
8,504 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB 4.491551e-05
8,956 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 4.4188719e-05
8,992 Processing Proximity Relations in Road Networks 2010 SIGMOD 4.4111332e-05
9,197 SkyGraph: Retrieving Regions of Interest using Skyline Subgraph Queries 2017 VLDB 4.3723013e-05
9,453 TRACE: Real-time Compression of Streaming Trajectories in Road Networks 2021 VLDB 4.3363262e-05
11,005 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.1905499e-05
11,068 Efficient kNN Search in Public Transportation Networks 2024 VLDB 4.1905499e-05
12,180 Finding Shortest Path on Land Surface 2011 SIGMOD 4.1905499e-05
12,287 Shortest Path Computation on Air Indexes 2010 VLDB 4.1905499e-05
13,538 Techniques for Similarity Searching in Multimedia Databases 2010 VLDB -
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank Cited Paper Year Venue Pagerank
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
391 Query Processing in Spatial Network Databases 2003 VLDB 0.00024560891
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
2,555 Distance Indexing on Road Networks 2006 VLDB 8.5505997e-05
7,279 A Population Analysis for Hierarchical Data Structures 1987 SIGMOD 4.7718422e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,052 On k-skip Shortest Paths 2011 SIGMOD 0.00014403922
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
6,497 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 5.0324877e-05
946 Path Oracles for Spatial Networks 2009 VLDB 0.00015117675
2,555 Distance Indexing on Road Networks 2006 VLDB 8.5505997e-05
6,203 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB 5.1552752e-05
391 Query Processing in Spatial Network Databases 2003 VLDB 0.00024560891
10,171 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD 4.1905499e-05
1,173 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013501079
597 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00019450818