Database Reference
In-Depth Information
i
−
1
Moreover, Pr
k
1
Pr
k
(
O
)
≥
p if there exists i
(
1
≤
i
≤
ω)
such that
∑
(
o
j
)
≥
p.
j
=
i
j
=
1
Pr
k
−
1
p
−
∑
(
o
j
)
Proof.
The first part: If there exists
i
such that
Pr
k
(
)
<
o
i
, then
ω
−
i
+
1
Pr
k
i
−
1
1
Pr
k
(ω
−
+
)
(
)
<
−
∑
(
)
i
1
o
i
p
o
j
.
j
=
Apparently,
Pr
k
Pr
k
(
o
1
)
≥···≥
(
o
ω
)
.
Thus, we have
Pr
k
o
i
)
≥
∑
j
=
i
Pr
k
(ω
−
i
+
1
)
(
(
o
j
)
.
Combining the above two inequalities, we have
∑
j
=
i
Pr
k
i
−
1
1
Pr
k
(
o
j
)
<
p
−
∑
(
o
j
)
.
j
=
Thus,
Pr
k
i
−
1
j
=
1
Pr
k
o
j
)+
∑
j
=
i
Pr
k
p
.
To prove the second part, we only need to notice
Pr
k
(
O
)=
∑
(
(
o
j
)
<
)=∑
j
=
1
Pr
k
(
O
(
o
j
)
≥
i
j
=
1
Pr
k
∑
(
o
j
)
≥
p
.
To use Theorem 6.1, for each stream
O
, if the last scanned instance in
O
satis-
fies one of the conditions in the theorem, the top-
k
probabilities of the remaining
instances of
O
do not need to be computed.
For an object uncertain stream
O
whose top-
k
probability in sliding window
W
is smaller than the threshold
p
, we can derive the maximum number of instances
scanned according to Theorem 6.1 as follows.
Corollary 6.2 (Maximum number of scanned instances).
For an uncertain stream
O, a top-k query Q
p
with probability threshold p, and all instances in W
(
O
)
sorted
in the ranking order o
1
≺···≺
o
ω
, the maximum number of instances scanned ac-
Pr
k
(
O
)
ω
+
cording to Theorem 6.1 is
1
.
p
Proof.
Let
o
t
(
t
>
1) be the first instance in
W
(
O
)
that satisfy Inequality 6.1. Then,
o
i
(1
≤
i
<
t
) does not satisfy Inequality 6.1. That is,
i
1
j
=
−
1
Pr
k
p
−
∑
(
o
j
)
p
ω
,
Pr
k
and
Pr
k
(
)
≥
(
)
≥
for 1
<
i
<
t
o
1
o
i
ω
−
i
+
1
By induction, it is easy to show that for 1
≤
i
<
t
i
j
=
1
Pr
k
p
ω
(
o
j
)
≥
i
×
t
−
1
Since
Pr
k
j
=
1
Pr
k
o
j
)+
∑
m
=
t
Pr
k
(
O
)=
∑
(
(
o
m
)
,wehave
t
1
j
=
1
Pr
k
−
ω
m
=
t
Pr
k
p
ω
Pr
k
(
o
j
)=
(
O
)
−
(
o
m
)
≥
(
t
−
1
)
×
Pr
k
(
O
)
Therefore,
t
≤
ω
+
1.
p
Our second pruning rule is based on the following observation.
Lemma 6.1 (Sum of top-
k
probabilities).
For a set of uncertain data streams
O
,a
top-k query Q
k
, and a sliding window W
t
Pr
k
ω
(
O
)
,
(
O
)=
k.
∑
O
∈O
