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

Summary: VoR-Tree blends R-tree indexing with Voronoi diagrams to speed NN queries. Coarse R-tree nodes reach the search region in log time, while Voronoi cells tile it to prune candidates, yielding better I/O complexity than prior NN methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10058
Venue: VLDB
Year: 2010
Pagerank: 5.2690256e-05
Overall Rank: 5,917 | 58.88%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Mehdi Sharifzadeh
2. Cyrus Shahabi

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,721	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9647585e-05
8,928	Processing Moving kNN Queries Using Influential Neighbor Sets	2015	VLDB	4.4229886e-05
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3544778e-05
11,660	Top-k Queries over Digital Traces	2019	SIGMOD	4.1905499e-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.0032118946
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
597	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019450818
1,924	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010075677
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-05
2,457	The Spatial Skyline Queries	2006	VLDB	8.7618183e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,276	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1905499e-05
4,880	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	5.8526687e-05
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
1,512	Indexing Land Surface for Efficient kNN Query	2008	VLDB	0.00011582099
9,307	Range-based Obstructed Nearest Neighbor Queries	2016	SIGMOD	4.3544778e-05
2,687	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.3079951e-05
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
597	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019450818