A reverse k-nearest neighbors (RkN N) 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 RkN N on uncertain data. A probabilistic RkN N (PRkN N) query retrieves all the objects that have higher probabilities than a user-specified threshold to be the RkN N of q. The previous work for answering PRN N query are mainly based on the distance relationship between uncertain objects, and are inapplicable for PRkN N when k ＞ 1. In this paper, we design a novel algorithm for PRkN N 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.
展开▼
