Parallel Skyline Computation on Multicore

With the advent of multicore processors, it has become imperative to write par-allel programs if one wishes to exploit the next generation of processors. This paper deals with skyline computation as a case study of parallelizing database op-erations on multicore architectures. First we parallelize three sequential skyline algorithms, BBS, SFS, and SSkyline, to see if the design principles of sequential skyline computation also extend to parallel skyline computation. Then we de-velop a new parallel skyline algorithm PSkyline based on the divide-and-conquer strategy. Experimental results show that all the algorithms successfully utilize multiple cores to achieve a reasonable speedup. In particular, PSkyline achieves a speedup approximately proportional to the number of cores when it needs a parallel computation the most