Parallelization of skyline probability computation over uncertain preferences

Query processing over uncertain preferences is very common in real-life situations, because many times, we cannot model users' preferences as strict partial orders. In this paper, we investigate skyline queries over uncertain preferences. The latest state-of-the-art algorithm, called Usky-base algorithm, makes significant advances. However, it still needs to be perfected in 2 aspects. (1) Theoretic analysis: The correctness of the algorithm is not fully verified. (2) Efficiency: Due to the heavy calculation introduced by adopting inclusion-exclusion principle to express the skyline probability, it needs massive time when computing skyline probabilities for large data sets. To address the above 2 concerns, we first review the Usky-base algorithm and lemmas it based on. Then we propose a novel parallel algorithm, called Parallel-sky, to compute skyline probability of a given object. Moreover, we propose an adding algorithm and a deleting algorithm to deal with dynamic scenarios where new objects are added in and outdated objects are deleted out. Furthermore, we extend our algorithm from computing skyline probability of a given object to all objects in a data set. We conduct extensive experiments on real and synthetic data sets to validate the effectiveness and efficiency of our proposals.