Parallel Skyline Computation for Partially Ordered Domains
Bo Yin, Ke Gu · 2017
The skyline queries help users handle the huge amount of available data by finding a set of interesting points. As the dataset sizes are constantly increasing and skyline queries are computationally expensive, it is critical to compute such queries by utilizing parallelism. Existing works deal exclusively with the totally ordered attribute domains. In this paper, we present a framework, named PSLP, for parallel skyline evaluation for data with both totally and partially ordered domains.We introduce a new partial-to-order mapping scheme that guarantees the correctness of the mapping by preserving incomparability and preference with low mapping cost. We also propose a novel logical partitioning for parallel processing where data space are partitioned according to their incomparability and preference relationships by using a pivot point. The logical partitioning can prune away partitions that do not contain any skyline point at the partitioning processing. An extensive performance evaluation confirms the efficiency and effectiveness of the proposed approach.