On processing reverse k-skyband and ranked reverse skyline queries

Y. Gao, Q. Liu, B. Zheng, L. Mou, G. Chen, Qing Li

Research output: Journal article publicationConference articleAcademic researchpeer-review

22 Citations (Scopus)

Abstract

© 2014 Elsevier Inc. All rights reserved.In this paper, for the first time, we identify and solve 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 RkSB retrieval, and then propose five 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, and employ pre-computation, reuse and pruning techniques to boost the query efficiency. In addition, we extend our solutions to tackle an interesting variant of reverse skyline queries, namely, ranked reverse skyline (RRS) query where, given a data set P, a parameter K, and a preference function f, the goal is to find the K reverse skyline points that have the minimal score according to the user-specified function f. Extensive experiments using both real and synthetic data sets demonstrate the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms under a variety of experimental settings.
Original languageEnglish
Pages (from-to)11-34
Number of pages24
JournalInformation Sciences
Volume293
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes

Keywords

  • Algorithm
  • k-skyband
  • Query processing
  • Ranked reverse skyline
  • Reverse
  • Skyline

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Theoretical Computer Science
  • Software
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Cite this