Scalable Parallelization of Skyline Computation for Multi-core Processors

Research output: Research - peer-reviewArticle in proceedings

  • Sean Chester
  • Darius Sidlauskas
    Darius SidlauskasEcole Polytechnique de LausanneDenmark
  • Ira Assent
  • Kenneth Sejdenfaden Bøgh
    Kenneth Sejdenfaden BøghDenmark
The skyline is an important query operator for multi-criteria decision making. It reduces a dataset to only those points that offer optimal trade-offs of dimensions. In general, it is very expensive to compute. Recently, multi-core CPU algorithms have been proposed to accelerate the computation of the skyline. However, they do not sufficiently minimize dominance tests and so are not competitive with state-of-the-art sequential algorithms.

In this paper, we introduce a novel multi-core skyline algorithm, Hybrid, which processes points in blocks. It maintains a shared, global skyline among all threads, which is used to minimize dominance tests while maintaining high throughput. The algorithm uses an efficiently-updatable data structure over the shared, global skyline, based on point-based partitioning. Also, we release a large benchmark of optimized skyline algorithms, with which we demonstrate on challenging workloads a 100-fold speedup over state-of-the-art multi-core algorithms and a 10-fold speedup with 16 cores over state-of-the-art sequential algorithms.
Original languageEnglish
Title of host publication31st IEEE International Conference on Data Engineering (ICDE 2015)
Number of pages12
PublisherIEEE Computer Society Press
Publication year2015
Pages1083 - 1094
DOIs
StatePublished - 2015
EventInternational Conference on Data Engineering - Seoul, Korea, Republic of
Duration: 13 Apr 201517 Apr 2015
Conference number: 31

Conference

ConferenceInternational Conference on Data Engineering
Nummer31
LandKorea, Republic of
BySeoul
Periode13/04/201517/04/2015

    Research areas

  • skyline, multicore, Parallel algorithms, Query processing

See relations at Aarhus University Citationformats

ID: 82060074