Abstract-The skyline is an important query operator for multi-criteria decision making. It reduces a dataset to only those points that ofTer optimal trade-offs of dimensions. In general, it is very expensive to compute. Recently, multicore 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 multicore skyline algo rithm, Hybrid, which processes points in blocks. It maintains a shared, global skyline among all threads, which is used to min imize 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 multicore algorithms and a lO-fold speedup with 16 cores over state-of-the-art sequential algorithms.
Hybrid REF applies tiling and point-based partitioning.
Scalable parallelization of skyline computation for multi-core processors
2015 IEEE 31st International Conference on Data Engineering
2015 IEEE 31st International Conference on Data Engineering
Computer Science