Parallel multi-level preference computation

Given a data set, a top-k Skyline query returns the k most interesting elements of the Skyline query based on some kind of user-defined preference. That means, sometimes not only the Pareto frontier is of interest, but also the stratum, the level, behind the Skyline to get exactly the top-k objects from a partially ordered set stratified into subsets of non-dominated tuples. In this paper, we extend the definition of top-k Skyline to form multi-level Skyline sets. Multi-level Skylines are a variant of top-k Skylines which do not stop after k tuples, but compute all Skyline levels. We present a parallel algorithm for multi-level Skyline computation on multi-core architectures and demonstrate through extensive experimentation on synthetic and real data sets that our algorithms can result in a significant performance advantage over existing techniques