Premium
Parallelization of group‐based skyline computation for multi‐core processors
Author(s) -
Zhu Haoyang,
Zhu Peidong,
Li Xiaoyong,
Liu Qiang,
Xun Peng
Publication year - 2017
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4195
Subject(s) - skyline , computer science , parallel computing , speedup , computation , multi core processor , set (abstract data type) , group (periodic table) , theoretical computer science , algorithm , data mining , programming language , chemistry , organic chemistry
Summary Skyline computation is particularly useful in multi‐criteria decision‐making applications. However, it is inadequate to answer queries that need to analyze not only individual points but also groups of points. Compared to the traditional skyline computation, computing group‐based skyline is much more complicated and expensive. This computational challenge promotes us to use modern computing platforms to accelerate the computation. In this paper, we introduce a novel multi‐core algorithm to compute group‐based skyline. We first compute the skyline layers of a data set in parallel, which are a critical intermediate result. In the algorithm, we maintain an efficiently updatable data structure for the shared global skyline layers, which is used to minimize dominance tests and maintain high throughput. Then we design an efficient parallel algorithm to find group‐based skyline based on the skyline layers. Extensive experimental results on real and synthetic data sets show that our algorithms achieve 10‐fold speedup with 16 parallel threads over state‐of‐the‐art sequential algorithms on challenging workloads.