Math @ Duke

Publications [#235366] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; HarPeled, S; Phillips, JM; Yi, K; Zhang, W, Nearest neighbor searching under uncertainty II,
Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems
(2013),
pp. 115126 [doi]
(last updated on 2017/12/12)
Abstract: Nearestneighbor (NN) search, 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, locationbased 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 distribution function. We 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 NN. We also present some experimental results to demonstrate the effectiveness of our approach. Copyright 2013 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

