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: 10057
Venue: VLDB
Year: 2010
Pagerank: 5.2739511e-05
Overall Rank: 5,917 | 58.84%
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,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05
8,925	Processing Moving kNN Queries Using Influential Neighbor Sets	2015	VLDB	4.427232e-05
9,309	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	4.3571035e-05
11,655	Top-k Queries over Digital Traces	2019	SIGMOD	4.1945683e-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.0032169493
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
598	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019474545
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
1,933	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010038508
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
2,457	The Spatial Skyline Queries	2006	VLDB	8.769229e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,268	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.1945683e-05
4,960	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	5.7987607e-05
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
1,514	Indexing Land Surface for Efficient kNN Query	2008	VLDB	0.00011593275
9,307	Range-based Obstructed Nearest Neighbor Queries	2016	SIGMOD	4.3571035e-05
2,725	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	8.2294908e-05
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
598	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00019474545