Bounds on skyline probability for databases with uncertain preferences

摘要: For determining skyline objects for an uncertain database with preferences, it is necessary to compute the probability of a given object respect other objects. The problem boils down computing union events from probabilities all possible joint probabilities. Linear Bonferroni bound concerned bounds on partial information. We use this technique estimate and propose polynomial-time algorithm sharp upper bound. show that information does not affect quality solution but helps in improving efficiency. formulate as Programming Problem (LPP) characterize set feasible points believed contain extreme LPP. maximization objective function over equivalent bi-polar quadratic optimization problem. spectral relaxation solve proposed O ( n 3 ) time complexity first ever determine probability. computed by our almost same deterministic algorithm. Experimental results are presented corroborate claim. In paper we three different probability.Computation using these more accurate than earlier sampling based technique.Our determines exact method.We validate hypothesis experiments real synthetic datasets.