Publication Type

Journal Article

Version

acceptedVersion

Publication Date

2-2015

Abstract

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.

Keywords

skyline, reverse k-skyband, ranked reverse skyline, query processing, algorithm

Discipline

Computer Sciences | Databases and Information Systems | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

Information Sciences

Volume

293

First Page

11

Last Page

34

ISSN

0020-0255

Identifier

10.1016/j.ins.2014.08.052

Publisher

Elsevier

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.ins.2014.08.052

Download

Share

COinS