Pre-computed Region Guardian Sets Based Reverse kNN Queries

Wei Song, Jianbin Qin, Wei Wang, Muhammad Aamir Cheema

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given a set of objects and a query q, a point p is q’s reverse k nearest neighbour (RkNN) if q is one of p’s k-closest objects. RkNN 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 RkNN results when running the filtering phase, which deteriorates the query performance. In this paper, we propose a novel RkNN 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 Rk′NN results are only affected by the objects in R’s guardian set, where k′≤k . The advantage of this approach is that the results of a query q∈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 RkNN.
Original languageEnglish
Title of host publication21st International Conference on Database Systems for Advanced Applications
Place of PublicationDallas, Texas, USA
PublisherSpringer, Cham
Number of pages15
ISBN (Electronic)978-3-319-32049-6
ISBN (Print)978-3-319-32048-9
Publication statusPublished - 25 Mar 2016
Event21st International Conference on Database Systems for Advanced Applications - Dallas, United States
Duration: 16 Apr 201619 Apr 2016


Conference21st International Conference on Database Systems for Advanced Applications
Abbreviated titleDASFAA 2016
CountryUnited States
Internet address

Cite this