Database Reference
In-Depth Information
6.1.2.1 Compatible Dominant Sets
O
that is in a window
W
t
, the top-
k
probability of
o
depends
on only the number of instances from streams other than
O
that precede
o
in the
ranking order. The ordering among those instances does not matter. Therefore, for
an instance
o
For an instance
o
∈
W
t
+
1
, if we can identify an instance
o
in either
W
t
or
W
t
+
1
such
that
o
and
o
are compatible in terms of number of other preceding instances, then
we can derive the top-
k
probability of
o
using that of
o
directly. Technically, we
introduce the concept of compatible dominant sets.
∈
Definition 6.3 (Compatible dominant sets).
Let
o
∈
O
be an instance that is in
window
W
t
+
1
and
DS
t
+
1
be the dominant set of
o
in
W
t
+
1
. For an instance
o
1
∈
(
o
)
O
, if for any stream
O
=
and dominant set
DS
(
o
1
)
O
, the number of instances from
O
in
DS
t
+
1
are the same,
DS
t
+
1
are called
compatible dominant sets
. Please note that
o
may be the same instance as
o
1
, and
DS
(
o
)
and that in
DS
(
o
)
(
o
)
and
DS
(
o
1
)
can be in
W
t
or
W
t
+
1
. We consider
DS
t
+
1
(
o
1
)
(
o
)
and itself trivial compatible
dominant sets.
Following with the Poisson binomial recurrence (Theorem 5.2), we immediately
have the following result.
Theorem 6.3 (Compatible dominant sets).
If DS
t
+
1
(
o
)
and DS
(
o
1
)
are compat-
DS
t
+
1
and Pr
k
ible dominant sets, for any j
≥
0
,Pr
(
(
o
)
,
j
)=
Pr
(
DS
(
o
1
)
,
j
)
(
o
)=
Pr
k
.
Proof.
If
DS
t
+
1
(
o
1
)
(
o
)
and
DS
(
o
1
)
are compatible dominant sets, then for any stream
O
(
o
O
),
Pr
O
∈
DS
t
+
1
O
∈
,
o
1
∈
[
(
o
)] =
Pr
[
DS
(
o
1
)]
. Thus, following with Theo-
k
−
1
DS
t
+
1
k
−
1
. Therefore,
Pr
k
rem 5.2, we have
∑
0
Pr
(
(
o
)
,
i
)=∑
0
Pr
(
DS
(
o
1
)
,
j
)
(
o
)=
i
=
j
=
Pr
k
(
o
1
)
.
Compatible dominant sets can be employed directly to reduce the computation
in window
W
t
+
1
using the results in window
W
t
and those already computed in
window
W
t
+
1
. For any instance
o
, if the dominant set of
o
in
W
t
+
1
is compatible to
some dominant set of
o
1
, then the top-
k
probability of
o
in
W
t
+
1
is the same as
o
1
.
No recurrence computation is needed for
o
in
W
t
+
1
.
When the data streams evolve slowly, the instances from a stream may have a
good chance to be ranked in the compatible places. Using compatible dominant sets
can capture such instances and save computation.
Now, the problem becomes how to find compatible dominant sets quickly. Here,
we give a fast algorithm which can be integrated to the top-
k
probability computa-
tion.
For each sliding window
W
t
, we maintain the sorted list of instances in the
window. When the window slides, we update the sorted list in two steps. First, we
insert the new instances into the sorted list, but still keep the expired instances. We
call the sorted list after the insertions the
expanded sorted list
.
We use an
n
-digit bitmap counter
c
(
O
)
[
1
]
,...,
c
[
n
]
, where
n
is the number of streams.
At the beginning,
c
[
i
]=
0 for 1
≤
i
≤
n
. We scan the expanded sorted list in the
