Database Reference
In-Depth Information
Ranked list of the instances at time
t
and
t
+
1
a
2
,
a
1
,
c
1
,
a
3
,
a
4
,
d
3
,
c
4
,
c
2
,
d
2
,
b
1
,
b
4
,
b
2
,
d
1
,
d
4
,
c
3
,
b
3
(a) The expanded sorted list.
Instance Counter=[A,B,C,D]
a
2
[0, 0, 0, 0]
a
1
[1, 0, 0, 0]
c
1
[1, 0, 1, 0]
a
3
[1, 0, 1, 0]
a
4
[0, 0, 1, 0]
d
3
[0, 0, 1, 0]
c
4
[0, 0, 0, 0]
c
2
[0, 0, 0, 0]
d
2
[0, 0, 0, 0]
b
1
[0, 1, 0, 0]
b
4
[0, 0, 0, 0]
b
2
[0, 0, 0, 0]
d
1
[0, 0, 0, 1]
d
4
[0, 0, 0, 0]
c
3
[0, 0, 0, 0]
b
3
[0, 0, 0, 0]
(b) The bitmap counters.
Fig. 6.1
The sorted lists of instances in
SW
(
t
−
1
)
and
SW
(
t
)
.
ranking order. If an expired instance or a new instance
o
∈
O
i
is met, we set
c
[
i
]=
c
[
i
]
⊕
1.
For an instance
o
O
i
in the expanded list such that
o
is in both
W
t
and
W
t
+
1
,if
∈
[
]
all the bitmap counters, except for
c
i
, are 0 right before
o
is read, then, for every
instance
o
∈
,
o
≺
(
=
)
o
in the expanded sorted list, one of the following
three cases may happen: (1)
o
appears in both
W
t
O
j
i
j
and
W
t
+
1
; (2)
o
=
O
j
[
t
−
ω +
1
]
(i.e.,
o
appears in
W
t
o
; or (3)
o
=
O
j
[
only) and the new instance
O
j
[
t
+
1
]
≺
t
+
1
]
(i.e., appears in
W
t
+
1
only) and the expired instance
O
j
[
t
−
ω +
1
]
≺
o
. In all the
three cases,
DS
t
and
DS
t
+
1
(
o
)
(
o
)
are compatible if
o
does not arrive at time
t
+
1.
1, then we check the left and the right neighbors of
o
in
the expanded sorted list. If one of them
o
is from the same stream as
o
, then
DS
If
o
arrives at time
t
+
(
o
)
o
)
and
DS
are compatible.
We conduct Poisson recurrence for only instances which are in
W
t
+
1
(
and do
not have a compatible dominance set. Otherwise, they are expired instances or their
top-
k
probabilities can be obtained from the compatible dominant sets immediately.
After one scan of the expanded sorted list, we identify all compatible dominant sets
and also compute the top-
k
probabilities. Then, we remove from the expanded sorted
list those expired instances. The current sliding window is processed. We are ready
to slide the window to the next time instant
(
O
)
(
t
+
2
)
.
