Work-efficient parallel skyline computation for the GPU

摘要: The skyline operator returns records in a dataset that provide optimal trade-offs of multiple dimensions. State-of-the-art computation involves complex tree traversals, data-ordering, and conditional branching to minimize the number point-to-point comparisons. Meanwhile, GPGPU computing offers potential for parallelizing across thousands cores. However, attempts port algorithms GPU have prioritized throughput failed outperform sequential algorithms.In this paper, we introduce new algorithm, designed GPU, uses global, static partitioning scheme. With partitioning, can permit controlled exploit transitive relationships avoid most result is non-traditional SkyAlign, prioritizes work-efficiency respectable throughput, rather than maximal achieve orders magnitude faster performance.