Scalable Processing of Snapshot and Continuous Nearest-Neighbor Queries Over One-Dimensional Uncertain Data

In several emerging and important applications, such as location-based services, sensor monitoring and biological databases, the values of the data items are inherently imprecise. A useful query class for these data is the Probabilistic Nearest-Neighbor query (PNN), which yields the IDs of objects for being the closest neighbor of a query point, together with the objects' probability values. Previous studies showed that this query takes a long time to evaluate. To address this problem, the authors propose the Constrained Nearest-Neighbor query (C-PNN), which returns the IDs of objects whose probabilities are higher than some threshold, with a given error bound in the answers.