TY - JOUR
T1 - Nearest-neighbor searching under uncertainty II
AU - Agarwal, Pankaj K.
AU - Aronov, Boris
AU - Har-Peled, Sariel
AU - Phillips, Jeff M.
AU - Yi, Ke
AU - Zhang, Wuzhou
N1 - Funding Information:
Most of the work on this article was done while W. Zhang was at Duke University. P. K. Agarwal and W. Zhang were supported by the NSF under grants CCF-09-40671, CCF-10-12254, CCF-11-61359, and IIS-14-08846. B. Aronov was supported by NSF grants CCF-08-30691, CCF-11-17336, and CCF-12-18791, and by NSA MSP Grant H98230-10-1-0210. S. Har-Peled was supported by NSF grants CCF-09-15984 and CCF-12-17462. J. Phillips was supported by NSF CCF-1350888, IIS-1251019, and ACI-1443046. K. Yi was supported by HKRGC under grants GRF-621413, GRF-16211614, and GRF-16200415.
Publisher Copyright:
© 2016 ACM.
PY - 2016/10
Y1 - 2016/10
N2 - Nearest-neighbor 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 a 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 distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability and (ii) estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.
AB - Nearest-neighbor 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 a 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 distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability and (ii) estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.
KW - Approximate nearest neighbor
KW - Indexing uncertain data
KW - Probabilistic nearest neighbor
KW - Threshold queries
UR - http://www.scopus.com/inward/record.url?scp=84992168545&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84992168545&partnerID=8YFLogxK
U2 - 10.1145/2955098
DO - 10.1145/2955098
M3 - Article
AN - SCOPUS:84992168545
SN - 1549-6325
VL - 13
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 1
M1 - 3
ER -