On efficient reverse k-skyband query processing

Qing Liu, Yunjun Gao, Gang Chen, Qing Li, Tao Jiang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

14 Citations (Scopus)

Abstract

This paper, for the first time, addresses the problem of efficient reverse k-skyband (RkSB) query processing. Given a set P of multi-dimensional points and a query point q, an RkSB query returns all the points in P whose dynamic k-skyband contains q. We formalize the RkSB query, and then propose three algorithms for computing the RkSB of an arbitrary query point efficiently. Our methods utilize a conventional data-partitioning index (e.g., R-tree) on the dataset, as well as employ pre-computation and pruning techniques to improve the query performance. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 17th International Conference, DASFAA 2012, Proceedings
Pages544-559
Number of pages16
EditionPART 1
DOIs
Publication statusPublished - 11 May 2012
Externally publishedYes
Event17th International Conference on Database Systems for Advanced Applications, DASFAA 2012 - Busan, Korea, Republic of
Duration: 15 Apr 201218 Apr 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7238 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Database Systems for Advanced Applications, DASFAA 2012
Country/TerritoryKorea, Republic of
CityBusan
Period15/04/1218/04/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this