Pre-computed Region Guardian Sets Based Reverse kNN Queries
Wei Song, Jianbin Qin, Wei Wang, Muhammad Aamir Cheema
Published in DASFAA, 2016
Given a set of objects and a query q, a point p is q's reverse k nearest neighbour (R kk NN) if q is one of p's k-closest objects. R kk NN queries have received significant research attention in the past few years. However, we realise that the state-of-the-art algorithm, SLICE, accesses many objects that do not contribute to its RkNNRkNN results when running the filtering phase, which deteriorates the query performance. In this paper, we propose a novel R kk NN algorithm with pre-computation by partitioning the data space into disjoint rectangular regions and constructing the guardian set for each region R. We guarantee that, for each q that lies in R, its R k_k_ NN results are only affected by the objects in R's guardian set, where k_2kk_2k . The advantage of this approach is that the results of a query q_Rq_R can be computed by using SLICE on only the objects in its guardian set instead of using the whole dataset. Our comprehensive experimental study on synthetic and real datasets demonstrates the proposed approach is the most efficient algorithm for R kk NN.