Database Reference
In-Depth Information
Example 6.2 (Compatible dominant set). Figure 6.1(a) shows the expanded sorted
list of instances in sliding windows W
3
and W
t
+
1
in Table 2.3. At time t
+
1
, the
3
d
4
arrive.
In Figure 6.1(b), we show the values of the bitmap counters during the scan of
the expanded sorted list. Each instance inW
t
+
3
, except for d
3
, can find a compatible
dominant set. We only need to conduct the Poisson recurrence computation of d
3
in
W
t
+
1
3
instances a
1
,
b
1
,
c
1
,
d
1
expire, and new instances a
4
,
b
4
,
c
4
,
.
6.1.2.2 Pruning Using the Highest Possible Rank
Consider an instance
o
in a sliding window
W
t
. As the window slides towards future,
new instances arrive and old instances expire. As a result, the rank of
o
in the sliding
windows may go up or down.
However, the instances arriving later than
o
or at the same time as
o
would never
expire before
o
. In other words, the possible rank of
o
in the future sliding windows
is bounded by those instances “no older” than
o
.
Lemma 6.2 (Highest possible rank).
For an instance O
[
i
]
arriving at time i, in a
sliding window W
t
O
[
O
∈O,
O
=
ω
(
O
)
such that t
−
ω +
1
<
i
≤
t, let
R
O
[
i
]
=
{
j
]
|
. In any sliding windowW
t
such that t
>
,
≥
}
[
]
O
j
i
t, the rank of O
i
cannot be less
ω
than
R
O
[
i
]
+
1
.
Example 6.3 (Highest possible rank). Consider again the uncertain streams in Ta-
ble 2.3. In window W
3
, the rank of c
2
is
6
. Among the
8
instances with time-stamp
t
1
and t, there are
3
instances ranked better than c
2
. The highest possible rank
of c
2
in the future windows is
4
. In window W
t
+
1
, there are
5
instances arriving
no earlier than c
2
and ranked better than c
2
. The highest possible rank of c
2
in the
future windows is
6
.
−
The highest possible rank of
o
can be used to derive an upper bound of the top-
k
probability of
o
in the future sliding windows.
Theorem 6.4 (Highest possible top-
k
probability).
For an instance o in sliding
window W
t
ω
r
−
1
with the highest possible rank r
≥
k
ω
, let
ρ =
, where n is the
ω(
n
−
1
)
number of streams, in any windowW
t
t
≥
ω
(
t
)
,
n
j
k
1
j
=
0
−
1
ω
Pr
k
j
n
−
j
(
o
)
≤
ρ
(
1
−
ρ)
Proof.
Given
o
with the highest possible rank
r
, there are
r
1 instances from other
objects ranked better than
o
. The sum of membership probabilities of those instances
is
−
r
−
1
. The theorem follows with Lemma 5.15 directly.
ω
Corollary 6.3 (Pruning using highest possible rank).
For any instance o
∈
O, if
p and there exists p
o
such that Pr
k
p
o
, then Pr
k
∑
o
∈
O
p
o
<
(
o
)
≤
(
O
)
<
p.
