Research on Reverse Nearest Neighbor Queries Using Ranked Voronoi Diagram
Bohan Li, Xiaolin Qin · 2009
The reverse nearest neighbor query is a new issue in the spatial and security database theory and application. This paper answers the reverse nearest neighbor queries effectively using the properties of the Voronoi diagram and the space-dividing regions. The reverse nearest neighbors of the given query point can be acquired without computing its nearest neighbors every time by the query and dynamic updating algorithm using the ranked Voronoi diagram. Experiments on typical synthetic data sets confirm the efficiency and scalability of proposed algorithms compared with the Brute Force search and TPL approach.