Scalable Parallelization of Skyline Computation for Multi-core Processors

TY - GEN

T1 - Scalable Parallelization of Skyline Computation for Multi-core Processors

AU - Chester, Sean

AU - Sidlauskas, Darius

AU - Assent, Ira

AU - Bøgh, Kenneth Sejdenfaden

N1 - Conference code: 31

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - skyline

KW - multicore

KW - Parallel algorithms

KW - Query processing

U2 - 10.1109/ICDE.2015.7113358

DO - 10.1109/ICDE.2015.7113358

M3 - Article in proceedings

SP - 1083

EP - 1094

BT - 31st IEEE International Conference on Data Engineering (ICDE 2015)

PB - IEEE Computer Society Press

T2 - International Conference on Data Engineering

Y2 - 13 April 2015 through 17 April 2015

ER -