Nearest-neighbor searching under uncertainty II


Journal Article

© 2016 ACM. 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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Aronov, B; Har-Peled, S; Phillips, JM; Yi, K; Zhang, W

Published Date

  • October 1, 2016

Published In

Volume / Issue

  • 13 / 1

Electronic International Standard Serial Number (EISSN)

  • 1549-6333

International Standard Serial Number (ISSN)

  • 1549-6325

Digital Object Identifier (DOI)

  • 10.1145/2955098

Citation Source

  • Scopus