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 PaperResearchpeer-review

    2 Citations (Scopus)


    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. Rk′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 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 publicationDatabase Systems for Advanced Applications
    Subtitle of host publication21st International Conference, DASFAA 2016, Dallas, TX, USA, April 16–19, 2016, Proceedings, Part II
    EditorsShamkant B. Navathe, Xiaoyong Du, Weili Wu, X. Sean Wang, Shashi Shekhar, Hui Xiong
    Place of PublicationAG Switzerland
    Number of pages15
    ISBN (Electronic)9783319320496
    ISBN (Print)9783319320489
    Publication statusPublished - 2016
    EventDatabase Systems for Advanced Applications 2016 - Dallas, United States of America
    Duration: 16 Apr 201619 Apr 2016
    Conference number: 21st (Conference Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    ConferenceDatabase Systems for Advanced Applications 2016
    Abbreviated titleDASFAA 2016
    CountryUnited States of America
    Internet address


    • Guardian Set
    • Pre-computation
    • RkNN
    • SLICE

    Cite this