DBScholar

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
h8e903586f039a9c3
Venue
SIGMOD
Year
2008
Pagerank
0.00018151383
Overall Rank
447 | 97.00%
DOI
10.1145/1376616.1376623

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{samet_sigmod08,
        title = {{Scalable Network Distance Browsing in Spatial Databases}},
        author = {Samet, Hanan and Sankaranarayanan, Jagan and Alborzi, Houman},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376623},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376623},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank Citing Paper Year Venue Pagerank
953 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00012871412
991 Path Oracles for Spatial Networks 2009 VLDB 0.00012642908
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
1,650 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9739794e-05
2,196 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 8.8763791e-05
3,689 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0921741e-05
3,921 Effective Caching of Shortest Paths for Location-Based Services 2012 SIGMOD 6.9219828e-05
4,140 Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs 2016 SIGMOD 6.7824033e-05
4,636 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4902578e-05
4,676 TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks 2018 VLDB 6.4725032e-05
5,065 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 6.2880787e-05
5,531 Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets 2012 VLDB 6.0906872e-05
5,968 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB 5.9297183e-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,326 Nearest Keyword Search in XML Documents 2011 SIGMOD 5.5500332e-05
7,979 TRACE: Real-time Compression of Streaming Trajectories in Road Networks 2021 VLDB 5.4121567e-05
7,985 Shortest Path Computation with No Information Leakage 2012 VLDB 5.4109223e-05
8,069 Correlation Constraint Shortest Path over Large Multi-Relation Graphs 2019 VLDB 5.3929452e-05
8,668 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB 5.2905639e-05
8,718 Finding Shortest Path on Land Surface 2011 SIGMOD 5.2880532e-05
9,289 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 5.2012076e-05
9,322 Processing Proximity Relations in Road Networks 2010 SIGMOD 5.1937083e-05
9,542 SkyGraph: Retrieving Regions of Interest using Skyline Subgraph Queries 2017 VLDB 5.1612403e-05
11,557 LION: Fast and High-Resolution Network Kernel Density Visualization 2024 VLDB 4.9769913e-05
11,606 Efficient kNN Search in Public Transportation Networks 2024 VLDB 4.9769913e-05
12,771 Shortest Path Computation on Air Indexes 2010 VLDB 4.9769913e-05
14,041 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
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
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,681 Distance Indexing on Road Networks 2006 VLDB 8.1391297e-05
7,415 A Population Analysis for Hierarchical Data Structures 1987 SIGMOD 5.5316503e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,426 On k-skip Shortest Paths 2011 SIGMOD
2 28 Nearest Neighbor Queries 1995 SIGMOD
3 6,087 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD
4 991 Path Oracles for Spatial Networks 2009 VLDB
5 2,681 Distance Indexing on Road Networks 2006 VLDB
6 5,968 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB
7 459 Query Processing in Spatial Network Databases 2003 VLDB
8 10,658 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD
9 953 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB
10 678 Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases 2004 VLDB