基于概率的反向K最近邻高效查询算法研究

Research on efficiently reverse K nearest neighbor query algorithm based on probability

反向K最近邻查询需要确定以给定查询对象作为其k个最近邻之一的所有对象。然而由于大量应用需要处理未知数据,人们迫切需要能够处理未知对象的新算法。这里的主要问题是,一个对象属于RKNN结果集的事件不再是一个确定性事件,而是一个以一定概率成立的随机变量。对基于概率论的未知数据集反向K最近邻(PRKNN)搜索问题展开研究,以足够大的概率返回以查询对象为其最近邻的未知对象。基于一种新的考虑了距离相关性的修剪机制,提出一种PRNN高效查询算法。此外,还给出了如何将该算法扩展至PRKNN(其中k>1)查询处理。最后,将该算法与当前其他最新算法作比较,实验评估结果表明,该算法性能明显优于其他算法。

A reverse K-nearest neighbor query retrieves all objects having a given query object as one of their k nearest neighbors. However, due to the immense number of applications dealing with uncertain data, novel solutions to cope with uncertain objects are required. The main challenge here is that the event that an object belongs to an RKNN result set is no longer a predicate, but a random variable that may be true with some probability. This paper studied the problem of probabilistic reverse K-nearest neighbor （PRKNN） search in uncertain databases, which returned the uncertain objects having the query object as nearest neighbor with a sufficiently high probability. It proposed an algorithm for efficiently answering PRNN queries using new pruning mechanisms taking distance dependencies into account. Finally, it compared the algorithm to state-of the-art approaches recently proposed. Experimental evaluation shows that the approach is able to significantly outperform previous approaches.