Indexing Probabilistic Nearest-Neighbor Threshold Queries

Data uncertainty is inherent in many applications, including sensor networks, scientific data management, data integration, location-based applications, etc. One of common queries for uncertain data is the Probabilistic Nearest Neighbor (PNN) query that returns all uncertain objects with non-zero probabilities to be NN. In this paper, the authors study the PNN query with a probability Threshold (PNNT), which returns all objects with the NN probability greater than the threshold. Their PNNT query removes the assumption in all previous papers that the probability of an uncertain object always adds up to 1, i.e., they consider missing probabilities.