TY - GEN
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
PY - 2013
Y1 - 2013
N2 - Nearest-neighbor (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, 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; (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.
AB - Nearest-neighbor (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, 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; (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.
KW - Approximate nearest neighbor
KW - Indexing uncertain data
KW - Probabilistic nearest neighbor
KW - Threshold queries
UR - http://www.scopus.com/inward/record.url?scp=84880555742&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84880555742&partnerID=8YFLogxK
U2 - 10.1145/2463664.2465219
DO - 10.1145/2463664.2465219
M3 - Conference contribution
AN - SCOPUS:84880555742
SN - 9781450320665
T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
SP - 115
EP - 126
BT - PODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems
T2 - 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013
Y2 - 22 June 2013 through 27 June 2013
ER -