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.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.…
Author: | Markus EndresGND, Werner KießlingGND |
---|---|
URN: | urn:nbn:de:bvb:384-opus4-11427 |
Frontdoor URL | https://opus.bibliothek.uni-augsburg.de/opus4/1372 |
Series (Serial Number): | Reports / Technische Berichte der Fakultät für Angewandte Informatik der Universität Augsburg (2010-01) |
Type: | Report |
Language: | English |
Publishing Institution: | Universität Augsburg |
Release Date: | 2010/03/31 |
Tag: | Präferenz; Datenbank skyline; preference; database |
Institutes: | Fakultät für Angewandte Informatik |
Fakultät für Angewandte Informatik / Institut für Informatik | |
Fakultät für Angewandte Informatik / Institut für Informatik / Lehrstuhl für Datenbanken und Informationssysteme | |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Licence (German): | Deutsches Urheberrecht |