2013 | OriginalPaper | Buchkapitel
Probabilistic n-of-N Skyline Computation over Uncertain Data Streams
verfasst von : Wenjie Zhang, Aiping Li, Muhammad Aamir Cheema, Ying Zhang, Lijun Chang
Erschienen in: Web Information Systems Engineering – WISE 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Skyline operator is a useful tool in multi-criteria decision making in various applications. Uncertainty is inherent in real applications due to various reasons. In this paper, we consider the problem of efficiently computing probabilistic skylines against the most recent
N
uncertain elements in a data stream seen so far. Specifically, we study the problem in the
n
-of-
N
model; that is, computing the probabilistic skyline for the most recent
n
(∀
n
≤
N
) elements, where an element is a probabilistic skyline element if its skyline probability is not below a given probability threshold
q
. Firstly, an effective pruning technique to minimize the number of uncertain elements to be kept is developed. It can be shown that on average storing only
O
( log
d
N
) uncertain elements from the most recent
N
elements is sufficient to support the precise computation of all probabilistic
n
-of-
N
skyline queries in a
d
-dimension space if the data distribution on each dimension is independent. A novel encoding scheme is then proposed together with efficient update techniques so that computing a probabilistic
n
-of-
N
skyline query in a
d
-dimension space is reduced to
O
(
d
loglog
N
+
s
) if the data distribution is independent, where
s
is the number of skyline points. Extensive experiments demonstrate that the new techniques on uncertain data streams can support on-line probabilistic skyline query computation over rapid data streams.