For the low efficiency of skyline computation on enormous and high-dimensional datasets, a new multi-core parallel skyline algorithm, named MPSSI (Multi-core Parallel Skyline computation based on Sorting and Incomparability), is proposed. The given dataset is first pre-ordered to simplify the whole algorithm. Then the dataset space is divided into several disjoint regions via a carefully selected pivot point, and by the dominance relations among regions, the number of dominance testing is reduced. Finally, all functions in MPSSI have been paralleled on multi-core platform to improve efficiency. MPSSI is characterized by simple process, good progressiveness and nice scalability. The experiment results show that, on enormous and high-dimensional datasets, MPSSI can significantly improve efficiency and almost reach linear relative speedup.
