Scalable parallelization of skyline computation for multi-core processors
- 1 April 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 1083-1094
Abstract
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, 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 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 multicore algorithms and a 10-fold speedup with 16 cores over state-of-the-art sequential algorithms.Keywords
This publication has 18 references indexed in Scilit:
- Scalable skyline computation using a balanced pivot selection techniqueInformation Systems, 2014
- Parallel computation of skyline and reverse skyline queries using mapreduceProceedings of the VLDB Endowment, 2013
- Efficient GPU-based skyline computation2013
- A survey of skyline processing in highly distributed environmentsThe VLDB Journal, 2011
- Parallel skyline computation on multicore architecturesInformation Systems, 2011
- Route skyline queries: A multi-preference path planning approach2010
- Evaluation of skyline algorithms in PostgreSQL2009
- Algorithms and analyses for maximal vector computationThe VLDB Journal, 2006
- Progressive skyline computation in database systemsACM Transactions on Database Systems, 2005
- The Skyline operator2002