Pre-computed region guardian sets based reverse kNN queries

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

Research output: Contribution to journalArticleOtherpeer-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. RkNN queries have received significant research attention in the past few years. However, we realize 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 RkNN results are only affected by the objects in R’s guardian set. 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. Besides, we raise two new useful variants of RkNN and propose algorithms. Our comprehensive experimental study on synthetic and real the proposed approaches are the most efficient algorithms for RkNN and its variants.

Original languageEnglish
Pages (from-to)242-251
Number of pages10
JournalData Science and Engineering
Issue number4
Publication statusPublished - Dec 2016


  • Guardian Set
  • Pre-computation
  • RkNN
  • Variants
  • Pre-computed region guardian sets based reverse kNN queries

    Song, W., Qin, J., Wang, W. & Cheema, M. A., 2016, Database Systems for Advanced Applications: 21st International Conference, DASFAA 2016, Dallas, TX, USA, April 16–19, 2016, Proceedings, Part II. Navathe, S. B., Du, X., Wu, W., Wang, X. S., Shekhar, S. & Xiong, H. (eds.). AG Switzerland: Springer, p. 98-112 15 p. (Lecture Notes in Computer Science ; vol. 9643).

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    3 Citations (Scopus)

Cite this