Reverse k Nearest Neighbors Query Processing: Experiments and Analysis
Reverse k Nearest Neighbors Query Processing: Experiments and Analysis
复制标题
DOI：
10.14778/2735479.2735492
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Shiyu Yang;M. A. Cheema;Xuemin Lin;Wei Wang-
中科院分区：
文献类型：
--
作者：
Shiyu Yang;M. A. Cheema;Xuemin Lin;Wei Wang-
给定一组用户、一组设施和一个查询设施q，反向k最近邻（RkNN）查询返回每个用户u，查询是其k个最近设施之一。RkNN查询已经在各种设置下被广泛研究，并且已经提出了许多复杂的算法来回答这些查询。然而，现有的实验研究受到一些限制。例如，一些研究通过对每个I/O收取固定罚款来估计I/O成本，我们表明这可能会产生误导。此外，现有的研究要么使用一个非常小的缓冲区或根本没有缓冲区，这使得一些算法处于严重的劣势。我们表明，这些算法的性能显着提高，即使是在一个小的缓冲区（包含100页）使用。最后，在每个现有的研究中，所提出的算法主要是比较它的前身，假设它是最好的算法，在我们的实验研究中所示的时间不一定是真的。出于这些限制，我们提出了一个全面的实验研究，解决这些限制，并比较了各种设置下的一些最显着的算法。此外，我们还提出了一个精心开发的过滤策略，显着提高TPL这是最流行的RkNN算法之一。具体而言，优化版本比原始版本快20倍，并将其I/O成本降低两倍。
Given a set of users, a set of facilities and a query facility q, a reverse k nearest neighbors (RkNN) query returns every user u for which the query is one of its k closest facilities. RkNN queries have been extensively studied under a variety of settings and many sophisticated algorithms have been proposed to answer these queries. However, the existing experimental studies suffer from a few limitations. For example, some studies estimate the I/O cost by charging a fixed penalty per I/O and we show that this may be misleading. Also, the existing studies either use an extremely small buffer or no buffer at all which puts some algorithms at serious disadvantage. We show that the performance of these algorithms is significantly improved even when a small buffer (containing 100 pages) is used. Finally, in each of the existing studies, the proposed algorithm is mainly compared only with its predecessor assuming that it was the best algorithm at the time which is not necessarily true as shown in our experimental study. Motivated by these limitations, we present a comprehensive experimental study that addresses these limitations and compares some of the most notable algorithms under a wide variety of settings. Furthermore, we also present a carefully developed filtering strategy that significantly improves TPL which is one of the most popular RkNN algorithms. Specifically, the optimized version is up to 20 times faster than the original version and reduces its I/O cost up to two times.