Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data
Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data
复制标题
DOI：
10.14778/2021017.2021024
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
T. Bernecker;Tobias Emrich;H. Kriegel;M. Renz;S. Zankl;Andreas Züfle
中科院分区：
文献类型：
--
作者：
T. Bernecker;Tobias Emrich;H. Kriegel;M. Renz;S. Zankl;Andreas Züfle
给定一个查询对象q，一个公共数据库中的反向最近邻（RNN）查询返回具有q作为其最近邻的对象。数据库面临的一个新挑战是处理不确定对象。在本文中，我们考虑概率反向最近邻（PRNN）查询，它返回的不确定对象有查询对象作为最近的邻居有足够高的概率。我们提出了一种算法，有效地回答PRNN查询使用新的修剪机制，考虑到距离依赖关系。我们比较我们的算法，最近提出的最先进的方法。我们的实验评估表明，我们的方法是能够显着优于以前的方法。此外，我们展示了我们的方法可以很容易地扩展到PRkNN（其中k > 1）查询处理，目前还没有有效的解决方案。
Given a query object q, a reverse nearest neighbor (RNN) query in a common certain database returns the objects having q as their nearest neighbor. A new challenge for databases is dealing with uncertain objects. In this paper we consider probabilistic reverse nearest neighbor (PRNN) queries, which return the uncertain objects having the query object as nearest neighbor with a sufficiently high probability. We propose an algorithm for efficiently answering PRNN queries using new pruning mechanisms taking distance dependencies into account. We compare our algorithm to state-of-the-art approaches recently proposed. Our experimental evaluation shows that our approach is able to significantly outperform previous approaches. In addition, we show how our approach can easily be extended to PRkNN (where k > 1) query processing for which there is currently no efficient solution.