From stars to galaxies: skyline queries on aggregate data

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

The skyline operator extracts relevant records from multidimensional databases according to multiple criteria. This operator has received a lot of attention because of its ability to identify the best records in a database without requiring to specify complex parameters like the relative importance of each criterion. However, it has only been defined with respect to single records, while one fundamental functionality of database query languages is aggregation, enabling operations over sets of records. In this paper we introduce aggregate skylines, where the skyline works as a filtering predicate on sets of records. This operator can be used to express queries in the form: return the best groups depending on the features of their elements, and thus provides a powerful combination of grouping and skyline functionality. We define a semantics for aggregate skylines based on a sound theoretical framework and study its computational complexity. We propose efficient algorithms to implement this operator and test them on real and synthetic data, showing that they outperform a direct SQL implementation of up to two orders of magnitude.
Original languageEnglish
Title of host publication International Conference on Extending Database Technology
EditorsGiovanna Guerrini , Norman W. . Paton
Number of pages12
PublisherAssociation for Computing Machinery
Publication year2013
Pages477-488
ISBN (print)978-1-4503-1597-5
DOIs
Publication statusPublished - 2013
EventInternational Conference on Extending Database Technology - Genoa, Italy
Duration: 18 Mar 201321 Mar 2013
Conference number: 16

Conference

ConferenceInternational Conference on Extending Database Technology
Nummer16
LandItaly
ByGenoa
Periode18/03/201321/03/2013

See relations at Aarhus University Citationformats

ID: 68451375