Voronoi-Based Nearest Neighbor Search for Multi-Dimensional Uncertain Databases

Nearest neighbor queries are the fundamental procedures for many similarity search and location-based query applications for location-based services. In particular, a nearest-neighbor query allows users to retrieve the most similar object to a given query object or to retrieve a location from a geospatial database that is closest to her current location. In recent studies it is shown that a Voronoi diagram is a data structure that is extremely efficient in exploring a local neighborhood in a geometric space. Given a set of points, a Voronoi diagram uniquely partitions the space into disjoint regions called Voronoi cells such that each cell is assigned to one single point.