Bi-directional Search for Skyline Probability

Computing the skyline probability of an object for a database, wherein the probability of

preferences

between pairs of data objects are uncertain, requires computing the probability of union of events from the probabilities of all possible joint probabilities. From the literature it can be seen that for a database of size

n

it requires computation of 2

n

joint probabilities of all possible combinations. All known algorithms for probabilistic skyline computation over uncertain preferences attempt to find inexact value of skyline probability by resorting to sampling or to approximation schemes. In this paper we use a concept called

zero-contributing set

of a power set lattice to denote portion of the lattice (a sub-lattice) such that the signed aggregate of joint probabilities corresponding to this set is zero. When such sets can be implicitly identified, the corresponding terms can be removed, saving substantial computational efforts. We propose an efficient heuristic that employs a bi-directional search traversing level wise the power set lattice from top and from bottom and prunes the exponential search space based on zero-contribution.