Efficient probabilistic reverse k-nearest neighbors query processing on uncertain data

A reverse k-nearest neighbors (RkNN) query returns all the objects that take the query object q as their k nearest neighbors. However, data are often uncertain in numerous applications. In this paper, we focus on the problem of processing RkNN on uncertain data. A probabilistic RkNN (PRkNN) query retrieves all the objects that have higher probabilities than a user-specified threshold to be the RkNN of q. The previous work for answering PRNN query are mainly based on the distance relationship between uncertain objects, and are inapplicable for PRkNN when k > 1. In this paper, we design a novel algorithm for PRkNN query to support arbitrary values of k on the basis of two pruning strategies, namely spatial pruning and probabilistic pruning. The spatial pruning rule is defined on both the distances and the angle ranges between uncertain objects. And an efficient upper bound of probability is estimated by the probabilistic pruning algorithm. Extensive experiments are conducted to study the performance of the proposed approach. The results show that our proposed algorithm has a better performance and scalability than the existing solution regarding the growth of k.