Efficient Evaluation of Semi-Skylines

Proceedings of the 5th International Workshop on Ranking in Databases in conjunction with VLDB 2011, Seattle, WA, USA, August 2011

Abstract: Skyline evaluation techniques (also known as Pareto preference queries) follow a common paradigm that eliminates data elements by finding other elements in a data set that dominate them. Nowadays already a variety of sophisticated Skyline evaluation techniques are known, hence Skylines are considered a well researched area. Besides these traditional Skyline queries the concept of Semi-Skylines exists. Semi-Skylines decompose a Skyline query into two halves. Semi-Skylines have some interesting applications, e.g. they can be used effectively for algebraic optimization of constrained Skyline queries or for a parallel computation of the Skyline on multi-core architectures. However, for the computation of Semi-Skylines no efficient algorithm exists. In this paper, we present the novel Staircube algorithm for Semi-Skyline evaluation.