DBScholar

Back to papers

Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases

Summary: Introduces a first-order Voronoi decomposition for spatial-network KNN, precomputing intra-region distances and only border-to-border inter-region distances to avoid global shortest-path materialization. Outperforms online and index-based methods by up to 10×, with 4× higher filter selectivity. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h9ce84b5cb6a96ed8
Venue
VLDB
Year
2004
Pagerank
0.00014843441
Overall Rank
677 | 95.45%
DOI
10.1016/B978-012088469-8.50074-7

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{kolahdouzan_vldb04,
        title = {{Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases}},
        author = {Kolahdouzan, Mohammad and Shahabi, Cyrus},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {840},
        doi = {10.1016/B978-012088469-8.50074-7},
        url = {https://doi.org/10.1016/B978-012088469-8.50074-7},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank Citing Paper Year Venue Pagerank
447 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018159715
739 PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks 2011 VLDB 0.00014333298
990 Path Oracles for Spatial Networks 2009 VLDB 0.00012648672
1,048 An Efficient and Scalable Approach to CNN Queries in a Road Network 2005 VLDB 0.00012303367
1,650 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9787032e-05
1,651 Indexing Land Surface for Efficient kNN Query 2008 VLDB 9.9787032e-05
1,652 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 9.9778734e-05
2,194 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 8.8805644e-05
2,681 Distance Indexing on Road Networks 2006 VLDB 8.142964e-05
4,674 TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks 2018 VLDB 6.4750983e-05
5,062 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 6.2910498e-05
5,519 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0968085e-05
5,966 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB 5.9325005e-05
7,323 Nearest Keyword Search in XML Documents 2011 SIGMOD 5.5524474e-05
7,396 Privacy-Aware Mobile Services over Road Networks 2009 VLDB 5.5366252e-05
8,369 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3450708e-05
8,662 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB 5.2928638e-05
8,895 Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks 2024 VLDB 5.2559789e-05
9,255 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 5.2056825e-05
9,280 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 5.2036709e-05
9,500 ROADTRACK: Scaling Location Updates for Mobile Clients on Road Networks with Query Awareness 2010 VLDB 5.1708619e-05
9,534 SkyGraph: Retrieving Regions of Interest using Skyline Subgraph Queries 2017 VLDB 5.1636848e-05
10,647 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD 4.9793485e-05
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.00051312804
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040370171
458 Query Processing in Spatial Network Databases 2003 VLDB 0.00017868943
826 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.0001363793
837 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013551047
1,407 Content-Based Image Indexing 1994 VLDB 0.00010749393
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,681 Distance Indexing on Road Networks 2006 VLDB
2 8,820 Spatial Queries with Two kNN Predicates 2012 VLDB
3 458 Query Processing in Spatial Network Databases 2003 VLDB
4 11,600 Efficient kNN Search in Public Transportation Networks 2024 VLDB
5 8,895 Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks 2024 VLDB
6 5,966 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB
7 5,519 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB
8 10,647 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD
9 6,107 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD
10 447 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD