Preliminary Exam Talks
Geometric Computing over Uncertain Data
|
Abstract
We have studied the nearest-neighbor searching problem, which returns the nearest neighbor of a query point in a set of points, in a probabilistic framework. Here, the location of each input point is specified as a probability distribution function. This talk will present new results on nearest neighbor searching under uncertainty, with two different problem formulations: expected nearest neighbor and probabilistic nearest neighbor. We focus on probabilistic nearest neighbor and present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability; (ii) estimating, within a specified additive error, the probability of a point being the nearest neighbor of a query point; (iii) 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 nearest neighbor. We also present some experimental results to demonstrate the effectiveness of our approach. We conclude the talk by proposing a few interesting problems as the future work.