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
3976
Venue
SIGMOD
Year
2008
Pagerank
0.00023310419
Overall Rank
433 | 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
945 Path Oracles for Spatial Networks 2009 VLDB 0.00015137526
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,513 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00011593275
1,526 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 0.00011512916
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
3,946 Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets 2012 VLDB 6.5993134e-05
4,111 Effective Caching of Shortest Paths for Location-Based Services 2012 SIGMOD 6.4427171e-05
4,193 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 6.37019e-05
4,745 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD 5.9573154e-05
4,854 TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks 2018 VLDB 5.8743687e-05
4,882 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 5.8548674e-05
5,250 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 5.6044961e-05
6,200 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB 5.1602201e-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
7,315 Nearest Keyword Search in XML Documents 2011 SIGMOD 4.7645064e-05
7,447 Shortest Path Computation with No Information Leakage 2012 VLDB 4.7273556e-05
7,897 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 4.6230399e-05
8,505 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB 4.4958064e-05
8,952 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 4.423107e-05
8,986 Processing Proximity Relations in Road Networks 2010 SIGMOD 4.4153655e-05
9,193 SkyGraph: Retrieving Regions of Interest using Skyline Subgraph Queries 2017 VLDB 4.3764958e-05
9,446 TRACE: Real-time Compression of Streaming Trajectories in Road Networks 2021 VLDB 4.3404859e-05
11,002 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.1945683e-05
11,065 Efficient kNN Search in Public Transportation Networks 2024 VLDB 4.1945683e-05
12,172 Finding Shortest Path on Land Surface 2011 SIGMOD 4.1945683e-05
12,279 Shortest Path Computation on Air Indexes 2010 VLDB 4.1945683e-05
13,525 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
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
389 Query Processing in Spatial Network Databases 2003 VLDB 0.00024620268
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
2,535 Distance Indexing on Road Networks 2006 VLDB 8.5864426e-05
7,284 A Population Analysis for Hierarchical Data Structures 1987 SIGMOD 4.7764316e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,054 On k-skip Shortest Paths 2011 SIGMOD 0.00014422699
47 Nearest Neighbor Queries 1995 SIGMOD 0.0007015885
6,503 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 5.0357715e-05
945 Path Oracles for Spatial Networks 2009 VLDB 0.00015137526
2,535 Distance Indexing on Road Networks 2006 VLDB 8.5864426e-05
6,200 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB 5.1602201e-05
389 Query Processing in Spatial Network Databases 2003 VLDB 0.00024620268
10,171 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD 4.1945683e-05
1,170 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013511856
598 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB 0.00019474545