Home Bookmarks Papers Blog

Nearest Neighbor Searching Under Uncertainty II

Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Jeff M. Phillips, Ke Yi, and Wuzhou Zhang.

Nearest-neighbor search (NN), which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability density function. We present efficient algorithms for

  1. computing all points that are nearest neighbors of a query point with nonzero probability;
  2. estimating, within a specified additive error, the probability of a point being the nearest neighbor of a query point;
  3. using it to return the point that maximizes the probability being the nearest neighbor, or all the points with probabilities greater than some threshold to be the \NN.
We also present a few experimental results to demonstrate the effectiveness of our approach.

Last modified: Sun Mar 24 14:00:48 CDT 2013