DefinePK

Abstract

Voronoi diagram has its advantages in Nearest Neighbors (NN) query. In order to effectively apply Voronoi diagram in NN query and its extension Continuous Nearest Neighbor (CNN) query so as to avoid the pitfalls of the existing approaches based on R-tree for these queries and achieve CNN query with arbitrary query trajectory, in this study, we first devise a data structure VR-tree, in which Voronoi diagram associated with the data space is embeded. Subsequently, an algorithm for nearest neighbor queries using VR-tree is proposed. After thoroughly analyzing the properties of Voronoi diagrams, an algorithm based on Voronoi diagrams for k-nearest neighbors queries is developed. This approach reduces the search space considerably by means of the properties of Voronoi diagram. Finally, we propose an algorithm for continuous nearest neighbor queries using Voronoi diagrams. It is well worth to mention that this approach achieves the continuous nearest neighbor queries with arbitrary query trajectory. The results of both analyzing in theory and experimental evaluation demonstrate that the proposed algorithms significantly outperform the previous ones.