Information Technology Reference
In-Depth Information
xyz
class value
011
no
010
yes
011
no
111
yes
100
yes
101
no
111
yes
000
ind
001
yes
000
ind
(a) A stream chunk of
10 elements.
(
x
,2,3) (
y
,2,3) (
z
,3,2)
yes
(
x
,2,1) (
y
,2,1) (
z
,0,3)
no
(
x
,2,0) (
y
,2,0) (
z
,2,0)
ind
(b) The resulting snapshot.
⇒
S
10
=
Fig. 1.
From data stream (a) to snapshot (b)
e
j
+
1
,...,
e
j
+
1
e
j
+
1
,...,
e
j
+
2
e
j
+
1
,...,
e
j
+
3
e
1
,...,
e
k
S
k
,
j
...
e
1
,...,
e
k
S
k
,
n
e
n
+
1
,...,
e
n
+
1
...
k
S
k
,
j
+
1
k
S
k
,
j
+
2
k
S
k
,
j
+
3
k
S
k
,
n
+
1
S
2
k
,
j
S
2
k
,
j
+
1
S
4
k
,
j
Fig. 2.
Snapshots and their order
Property 2.
Building a snapshot
S
k
requires
k
accesses to the data stream. Every ele-
ment is accessed only once. Computing a snapshot is linear to the
k
number of elements.
Figure 1 shows an example of snapshot creation. The latter implies only a single access
to every stream element. A snapshot is built incrementally accessing the data one by
one, and updating the respective counters. Properties 1 and 2 guarantee that a snapshot
requires a constant time and memory space, satisfying Requirements 1 and 2.
Snapshots of Higher Order.
The only concept of snapshot is not sufficient to guaran-
tee all the features needed for data managing and drift reaction. The concept of high-
order snapshot is necessary to maximize data availability for the mining task guaran-
teeing only one data access.
Definition 3 (High-order Snapshot).
Given an order value i
>
0
, a high-order snap-
shot, is obtained by summing h snapshots of i
−
1
order:
h
j
=
1
S
i
−
1
S
i
h
×
k
=
k
,
j
j
=
1
freq
j
a
,
k
,
c
i
−
1
, ∀
a
∈
A
,
c
∈
C
h
