Database Reference
In-Depth Information
6.1.1 Top-k Probabilities in a Sliding Window
Consider a set of uncertain data streams
O
=
{
O
1
,...,
O
n
}
and sliding window
W
t
.
W
t
)
in the sliding window. In this subsection, we consider how to rank the data streams
according to their instances in sliding window
W
t
ω
(
O
)
ω
(
O
i
)=
{
O
i
[
t
−
ω +
1
]
,...,
O
i
[
t
]
}
is the set of instances of
O
i
(
1
≤
i
≤
n
ω
(
O
)
. When it is clear from con-
text, we write
W
t
and
W
t
ω
(
O
)
ω
(
)
(
O
)
(
)
, respectively.
We reduce computing the top-
k
probability of a stream
O
into computing the
top-
k
probabilities of instances of
O
.
O
i
simply as
W
and
W
O
i
Definition 6.1 (Top-
k
probability of instance).
For an instance
o
and a top-
k
query
Q
k
, the
top-k probability
of
o
, denoted by
Pr
k
(
)
o
, is the probability that
o
is ranked
)=
{
w
∈W |
o
∈
Q
k
(
w
)
}
in the top-
k
lists in possible worlds. That is,
Pr
k
(
o
.
W
Following with Definitions 2.11 and 2.14, we have the following.
Corollary 6.1 (Top-
k
probability).
For an uncertain data stream O, a sliding win-
dowW
t
and a top-k query Q
k
,
ω
(
O
)
1
ω
Pr
k
∑
o
∈
W
t
Pr
k
∑
o
∈
W
t
Pr
k
(
O
)=
(
o
)
Pr
(
o
)=
(
o
)
.
ω
(
O
)
ω
(
O
)
We sort all instances according to their scores. Let
R
denote the ranking order
of instances. For two instances
o
1
o
2
if
o
1
is ranked before (i.e.,
better than)
o
2
in
R
. Clearly, the rank of an instance
o
of stream
O
in the possible
worlds depends on only the instances of other streams that are ranked better than
o
.
We capture those instances as the dominant set of
o
.
,
o
2
, we write
o
1
≺
Definition 6.2 (Dominant set).
Given a set of streams
O
, a sliding window
W
, and
a top-
k
query
Q
k
, for an instance
o
of stream
O
∈ O
, the
dominant set
of
o
is the
set of instances of streams in
O −{
O
}
that are ranked better than
o
, denoted by
o
∈
o
≺
DS
(
o
)=
{
W
(
O−
O
)
|
o
}
.
In a possible world
w
, an instance
o
is ranked the
i
-th place if and only if there
are
(
i
−
1
)
instances in
DS
(
o
)
appearing in
w
, and each of those instances is from a
unique stream.
Based on this observation, for instance
o
and stream
O
such that
o
O
,we
∈
denote by
O
≺
o
in a possible world
w
if there exists
o
∈
O
)
,
o
≺
o
, and
o
and
W
(
o
appear in
w
. Apparently, we have
Pr
1
ω
∑
o
)
O
)
O
≺
(
o
)=
Pr
(
Pr
(
o
)=
2
DS
(
o
)
∩
W
(
.
o
∈
o
∈
O
DS
(
o
)
,
from unique streams
appear in a possible world. Then, the top-
k
probability of
o
can be written as
Let
Pr
(
DS
(
o
)
,
i
)
be the probability that
i
instances in
DS
(
o
)
k
−
1
i
=
0
Pr
(
DS
(
o
)
,
i
)=
k
−
1
i
=
0
Pr
(
DS
(
o
)
,
i
)
.
1
ω
Pr
k
(
o
)=
Pr
(
o
)
