VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries

Summary: VoR-Tree hybridizes R-tree rectangles with Voronoi cells: logarithmic navigation reaches the NN search region, while fine-grained Voronoi tiling avoids irrelevant-node exploration. Supports NN variants with improved I/O complexity over prior methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10248
Venue: VLDB
Year: 2010
Pagerank: 6.0564961e-05
Overall Rank: 5,875 | 59.70%
DOI: 10.14778/1920841.1920997

Incoming Non-self Citations Over Time

Authors

1. Mehdi Sharifzadeh (Google)
2. Cyrus Shahabi (University of Southern California)

BibTeX Citation

@article{sharifzadeh_vldb10,
        title = {{VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries}},
        author = {Sharifzadeh, Mehdi and Shahabi, Cyrus},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {1231--1242},
        doi = {10.14778/1920841.1920997},
        url = {https://doi.org/10.14778/1920841.1920997},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	6.480347e-05
9,080	Processing Moving kNN Queries Using Influential Neighbor Sets	2015	VLDB	5.3251649e-05
9,356	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.282937e-05
11,850	Top-k Queries over Digital Traces	2019	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
546	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016734556
665	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00015167291
1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010218134
1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.5068846e-05
2,689	The Spatial Skyline Queries	2006	VLDB	8.2559825e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,463	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
2	4,711	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD
3	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD
4	277	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD
5	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
6	1,619	Indexing Land Surface for Efficient kNN Query	2008	VLDB
7	9,354	Range-based Obstructed Nearest Neighbor Queries	2016	SIGMOD
8	1,802	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB
9	28	Nearest Neighbor Queries	1995	SIGMOD
10	665	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB