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

.