Reverse k Nearest Neighbors Query Processing: Experiments and Analysis

Given a set of users, a set of facilities and a query facility q, a re-verse 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 so-phisticated algorithms have been proposed to answer these queries. However, the existing experimental studies suffer from a few limi-tations. For example, some studies estimate the I/O cost by charg-ing a fixed penalty per I/O and we show that this may be mislead-ing. Also, the existing studies either use an extremely small buffer or no buffer at all which puts some algorithms at serious disadvan-tage. We show that the performance of these algorithms is signif-icantly improved even when a small buffer (containing 100 pages) is used. Finally, in each of the existing studies, the proposed al-gorithm is mainly compared only with its predecessor assuming that it was the best algorithm at the time which is not necessar-ily 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 im-proves 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. 1