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: hebf9fde228104fd4
Venue: VLDB
Year: 2010
Pagerank: 6.0968085e-05
Overall Rank: 5,519 | 62.90%
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 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,835	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	6.3877419e-05
8,487	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.3322198e-05
9,255	Processing Moving kNN Queries Using Influential Neighbor Sets	2015	VLDB	5.2056825e-05
10,762	RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem	2026	VLDB	4.9793485e-05
12,150	Top-k Queries over Digital Traces	2019	SIGMOD	4.9793485e-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.001992968
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
677	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00014843441
1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010201796
1,956	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.3169059e-05
2,740	The Spatial Skyline Queries	2006	VLDB	8.0720377e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,754	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
2	4,797	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	279	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD
5	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
6	1,651	Indexing Land Surface for Efficient kNN Query	2008	VLDB
7	9,524	Range-based Obstructed Nearest Neighbor Queries	2016	SIGMOD
8	1,684	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB
9	28	Nearest Neighbor Queries	1995	SIGMOD
10	677	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB