Database Reference
In-Depth Information
Algorithm 6.1
The exact algorithm.
Input:
a set of uncertain streams
O
, a sliding window width
ω
, a time instant
t
+
1, a top-
k
query
Q
p
, and a probability threshold
p
Output:
Answer to top-
k
query in window
W
t
+
1
ω
Method:
1: insert the new instances arriving at time
t
1 into the sorted list in window
W
t
ω
+
;
2: initialize
Pr
k
;
3: compute the highest possible top-
k
probability for each stream
O
i
(
O
i
)=
0 for each stream
O
i
∈O
∈ O
, remove
O
i
from con-
sideration if it fails the probability threshold;
4: set counter
C
[
i
]=
0 for each stream
O
i
∈O
;
5:
for all
o
in the expanded sorted list
do
6:
update the corresponding counter if
o
is expired or new;
compute
DS
(
o
)
;
7:
if
DS
(
o
)
has a compatible dominant set
then
8:
obtain
Pr
k
9:
(
o
)
directly;
10:
else
11:
compute the probabilities
Pr
(
DS
(
I
)
,
j
)
(0
≤
j
<
k
);
12:
end if
Pr
k
Pr
k
Pr
k
13:
(
O
)=
(
O
)+
(
o
)
;
if
Pr
k
14:
(
O
)
≥
p
then
15: output
O
;
16:
end if
17: check whether
o
can be used to prune some unread instances;
18:
if
all objects either are output or fail the probability threshold
then
19: exit;
20:
end if
21:
end for
space to maintain the highest possible rank for an instance. The
overall space consumption is
O
We need
O
(
1
)
for a sliding window. Each time when new
instances arrive, the highest possible ranks of all old instances are updated. The
highest possible top-
k
probability of each stream is updated accordingly. This can
be integrated into the top-
k
probability computation. For a stream
O
, once the upper
bound of
Pr
k
(
n
ω)
(
)
fails the threshold, all instances in
O
do not need to be checked in
the current window.
Algorithm 6.1 shows the complete exact algorithm. Compatible dominant sets
can help to reduce the computation cost, however, although it works well in prac-
tice, in the worst case, the new instances may be ranked far away from the expired
instances of the same stream, and thus no compatible dominant sets can be found.
Thus, the time complexity of processing a sliding window, except for the first one, is
O
O
kn
2
(
ω +
n
log
(
n
ω))
, where
O
(
n
log
(
n
ω))
is the cost to insert the
n
new instances
into the sorted list.
