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
9382
Venue
VLDB
Year
2004
Pagerank
0.00015167291
Overall Rank
665 | 95.44%
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
433 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018532516
731 PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks 2011 VLDB 0.00014537965
968 Path Oracles for Spatial Networks 2009 VLDB 0.00012901559
1,025 An Efficient and Scalable Approach to CNN Queries in a Road Network 2005 VLDB 0.00012578515
1,618 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00010207737
1,619 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00010207737
1,620 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00010206305
2,153 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 9.0762376e-05
2,629 Distance Indexing on Road Networks 2006 VLDB 8.3265243e-05
4,573 TOAIN: A Throughput Optimizing Adaptive Index for Answering Dynamic kNN Queries on Road Networks 2018 VLDB 6.6226156e-05
4,937 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 6.4350791e-05
5,851 k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation 2016 VLDB 6.0659596e-05
5,875 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0564961e-05
7,180 Nearest Keyword Search in XML Documents 2011 SIGMOD 5.6798251e-05
7,246 Privacy-Aware Mobile Services over Road Networks 2009 VLDB 5.6637035e-05
8,200 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.4677285e-05
8,493 Top-K Nearest Keyword Search on Large Graphs 2013 VLDB 5.4142883e-05
8,731 Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks 2024 VLDB 5.3766157e-05
9,080 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 5.3251649e-05
9,111 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 5.3221578e-05
9,321 ROADTRACK: Scaling Location Updates for Mobile Clients on Road Networks with Query Awareness 2010 VLDB 5.289545e-05
9,358 SkyGraph: Retrieving Regions of Interest using Skyline Subgraph Queries 2017 VLDB 5.2822032e-05
10,460 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD 5.093636e-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.00052102434
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040719947
449 Query Processing in Spatial Network Databases 2003 VLDB 0.0001826404
796 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00013932561
815 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013835761
1,384 Content-Based Image Indexing 1994 VLDB 0.00010957733
Previous Page 1 / 1 Next

Semantically Similar Papers

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