Database Reference
In-Depth Information
Proof.
Using the definition of top-
k
probability, we have
O
∈O
Pr
k
∑
w
∈W ,
o
∈
Q
k
(
O
)=
Pr
(
w
)
(
w
)
In a possible world
w
,
∑
o
∈
Q
k
Pr
(
w
)=
k
·
Pr
(
w
)
. Using Corollary 2.4, we have
(
w
)
∑
O
∈O
Pr
k
(
O
)=
k
∑
w
∈W
Pr
(
w
)=
k
.
Theorem 6.2 (Pruning by top-
k
probability sum).
Consider a set of uncertain
data streams
, a top-k query Q
p
with probability threshold p, and a sliding window
O
W
t
. Assume all instances in W
t
ω
(
O
)
ω
(
O
)
are scanned in the ranking order, and S
⊂
W
t
,Pr
k
ω
(
O
)
is the set of instances that are scanned. For a stream O
∈O
(
O
)
<
pif
∑
Pr
k
−
o
∈
S
Pr
k
o
))
.
(
o
)
<
p
−
(
k
(
o
∈
O
∩
S
Proof.
Following with Lemma 6.1, we have
∑
−
o
∈
S
Pr
k
Pr
k
o
)
.
(
o
)=
k
(
W
t
o
∈
ω
(
O
)
−
S
∑
o
∈
O
∩
S
Pr
k
−
∑
o
∈
S
Pr
k
o
))
If
(
o
)
<
p
−
(
k
(
, then
Pr
k
)=
∑
o
∈
O
Pr
k
(
O
(
o
)
=
∑
o
∈
O
∩
S
Pr
k
Pr
k
(
)+
∑
o
∈
O
∩
(
W
t
(
)
o
o
ω
(
O
)
−
S
)
−
∑
o
∈
S
Pr
k
o
)+
−
∑
o
∈
S
Pr
k
o
))
<
k
(
p
−
(
k
(
=
p
In summary, by sorting the instances in a sliding window in the ranking order and
scanning the sorted list once, we can compute the top-
k
probability for each stream,
and thus the exact answer to the top-
k
query on the window can be derived. The two
pruning rules can be used to prune the instances and the streams.
6.1.2 Sharing between Sliding Windows
Using the method described in Section 6.1.1, we can compute the exact answer to a
top-
k
query
Q
k
in one sliding window
W
t
. In the next time instant
(
t
+
1
)
, can we
reuse some of the results in window
W
t
to compute the answer to
Q
k
in window
W
t
+
1
?
In this subsection, we first observe the compatible dominant set property, and
then we explore sharing in computing answers to a top-
k
query on two consecutive
sliding windows.
