Parallelization of group‐based skyline computation for multi‐core processors. (6th June 2017)

• Record Type: Journal Article
• Authors: Zhu, Haoyang; Zhu, Peidong; Li, Xiaoyong; Liu, Qiang; Xun, Peng
• Is Part Of: Concurrency and computation. Volume 29:Number 18(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-06-06
• Subjects: group‐based skyline -- parallel queries -- performance evaluation -- skyline queries; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4195
• Languages: English
• ISSNs: 1532-0626

Abstract

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.