Parallelization of group-based skyline computation forrnmulti-core processors

摘要

Skyline computation is particularly useful in multi-criteriadecision-making applications.However,rnit is inadequate to answer queries that need to analyze not only individual points but also groups ofrnpoints. Compared to the traditional skyline computation, computing group-based skyline ismuchrnmore complicated and expensive. This computational challenge promotes us to usemodern computingrnplatforms to accelerate the computation. In this paper, we introduce a novel multi-corernalgorithm to compute group-based skyline. We first compute the skyline layers of a data set inrnparallel, which are a critical intermediate result. In the algorithm,wemaintain an efficiently updatablerndata structure for the shared global skyline layers, which is used to minimize dominance testsrnandmaintain high throughput. Thenwe design an efficient parallel algorithm to find group-basedrnskyline based on the skyline layers. Extensive experimental results on real and synthetic data setsrnshow that our algorithms achieve 10-fold speedup with 16 parallel threads over state-of-the-artrnsequential algorithms on challenging workloads.