Paper Info
Title
Bi-directional Search for Skyline Probability.
Abstract
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.
Year
DOI
Venue
2015
10.1007/978-3-319-14974-5_24
ALGORITHMS AND DISCRETE APPLIED MATHEMATICS (CALDAM 2015)
Field
DocType
Volume
Skyline,Heuristic,Joint probability distribution,Exponential search,Computer science,Algorithm,Sampling (statistics),Probabilistic logic,Power set,Computation
Conference
8959
ISSN
Citations 
PageRank 
0302-9743
3
0.41
References 
Authors
12
4
Name
Order
Citations
PageRank
Arun K. Pujari142048.20
Venkateswara Rao Kagita2598.13
Anubhuti Garg3110.90
Vineet Padmanabhan421625.90