Semi-skylines and skyline snippets

Skyline evaluation techniques (also known as Pareto preference queries) follow a common paradigm that eliminates data elements by finding other elements in the data set that dominate them. To date already a variety of sophisticated skyline evaluation techniques are known, hence skylines are considered a well researched area. Nevertheless, in this paper we come up with interesting new aspects. Our first contribution proposes so-called semi-skylines as a novel building stone towards efficient algorithms. Semi-skylines can be computed very fast by a new Staircase algorithm. Semi-skylines have a number of interesting and diverse applications, so they can be used for constructing a very fast 2-dimensional skyline algorithm. We also show how they can be used effectively for algebraic optimization of preference queries having a mixture of hard constraints and soft preference conditions. Our second contribution concerns so-called skyline snippets, representing some fraction of a full skyline. For very large skylines, in particular for higher dimensions, knowing only a snippet is often considered as sufficient. We propose a novel approach for efficient skyline snippet computation without using any index structure, by employing our above 2-d skyline algorithm. All our efficiency claims are supported by a series of performance benchmarks. In summary, semi-skylines and skyline snippets can yield significant performance advantages over existing techniques