The τ-Skyline for Uncertain Data.
Haitao Wang, Wuzhou Zhang · 2014
In this paper, we introduce the notion of τ-skyline as an alternative representation for uncertain skylines. Given a parameter τ ∈ [0,1] and a set P of n uncertain points in the plane, where each uncertain point Pi is described by a discrete probability distribution defined over k lo-cations, the τ-skyline region of P is the set of points q in the plane such that the probability of any Pi dominating q is at most τ, and the τ-skyline of P is the boundary of the τ-skyline region of P. We present an O(nk log(nk)) time algorithm for computing the τ-skyline of P. The τ-skyline probability of each Pi of P is defined to be the probability of Pi lying inside the τ-skyline region of P. We show that the τ-skyline probabilities of all Pi’s can be computed in O(nk log(nk)) time. Remarkably, our method is very simple and can be easily implemented, a huge potential interest for practice. 1