Parallelization of skyline probability computation over uncertain preferences

SummaryQuery 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, calledUsky‐basealgorithm, 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 adoptinginclusion‐exclusion principleto 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 theUsky‐basealgorithm and lemmas it based on. Then we propose a novel parallel algorithm, calledParallel‐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.