Publication Type

Journal Article

Version

publishedVersion

Publication Date

6-2014

Abstract

Given a D-dimensional data set P and a query point q, a reverse skyline query (RSQ) returns all the data objects in P whose dynamic skyline contains q. It is important for many real life applications such as business planning and environmental monitoring. Currently, the state-of-the-art algorithm for answering the RSQ is the reverse skyline using skyline approximations (RSSA) algorithm, which is based on the precomputed approximations of the skylines. Although RSSA has some desirable features, e.g., applicability to arbitrary data distributions and dimensions, it needs for multiple accesses of the same nodes, incurring redundant I/O and CPU costs. In this paper, we propose several efficient algorithms for exact RSQ processing over multidimensional datasets. Our methods utilize a conventional data-partitioning index (e.g., R-tree) on the dataset P, and employ precomputation, reuse, and pruning techniques to boost the query performance. In addition, we extend our techniques to tackle a natural variant of the RSQ, i.e., constrained reverse skyline query (CRSQ), which retrieves the reverse skyline inside a specified constrained region. Extensive experimental evaluation using both real and synthetic datasets demonstrates that our proposed algorithms outperform RSSA by several orders of magnitude under all experimental settings.

Keywords

Skyline, Reverse skyline, Constrained reverse skyline, Query processing, Algorithm

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

Expert Systems with Applications

Volume

41

Issue

7

First Page

3237

Last Page

3249

ISSN

0957-4174

Identifier

10.1016/j.eswa.2013.11.012

Publisher

Elsevier

Copyright Owner and License

Publisher

Additional URL

https://doi.org/10.1016/j.eswa.2013.11.012

Download

Share

COinS