Asymptotically Efficient Algorithms for Skyline Probabilities of Uncertain Data

Skyline computation is widely used in multicriteria decision making. As research in uncertain databases draws increasing attention, skyline queries with uncertain data have also been studied. Some earlier work focused on probabilistic skylines with a given threshold; Atallah and Qi [2009] studied the problem to compute skyline probabilities for all instances of uncertain objects without the use of thresholds, and proposed an algorithm with subquadratic time complexity. In this work, we propose a new algorithm for computing all skyline probabilities that is asymptotically faster: worst-case O(n root nlog n) time and O(n) space for 2D data; O(n(2-1/d) log(d-1) n) time and O(nlog(d-2) n) space for d-dimensional data. Furthermore, we study the online version of the problem: Given any query point p (unknown until the query time), return the probability that no instance in the given data set dominates p. We propose an algorithm for answering such an online query for d-dimensional data in O(n(1-1/d) log(d-1) n) time after preprocessing the data in O(n(2-1/d) log(d-1)) time and space.