Premium
Parallelization of skyline probability computation over uncertain preferences
Author(s) -
Zhu Haoyang,
Zhu Peidong,
Li Xiaoyong,
Liu Qiang,
Xun Peng
Publication year - 2017
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4201
Subject(s) - skyline , computer science , correctness , set (abstract data type) , object (grammar) , computation , data mining , result set , base (topology) , algorithm , theoretical computer science , artificial intelligence , programming language , mathematics , mathematical analysis
Summary 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.