Database Reference
In-Depth Information
these projections and as soon as
kW
values accumulate, we update the
k
local patterns for level
l
= 1. Then we can discard the
kW
projections
from level-0, but we keep the
k
level-1 projections. We proceed in the
same way for all other levels
l ≥
2.
Complexity
Compared to the batch computation, we need
O
k·Wk·
t
w
0
W
l
=
O
W
l−
1
time to compute the first
k
singular values and vectors
kt
of
X
(
w
0
,l
)
for
l
=1
,
2
,...
.For
l
= 0 we need
O
k
w
0
=
O
(
kt
)time.
Summing over
l
=0
,
1
,...,L
we get
O
(
kt
). With respect to space,
we need to buffer
w
0
points for
l
=0and
Wk
points for each of the
remaining
L
=
O
(log
t
) levels, for a total of
O
(
k
log
t
). Therefore, we
have the following
t
·
w
0
·
Lemma 5.14 (Streaming, hier. complexity)
Amortized cost is
O
(
k
)
per incoming point and total space is
O
(
k
log
t
)
.
Since
k
= 6, the update time is constant per incoming point and the
space requirements grow logarithmically with respect to the size
t
of the
series.
Table 5.2
summarizes the time and space complexity for each
approach.
Time
Space
Non-hier.
Hier.
Non-hier.
Hier
O
(
t
3
k
)
O
(
tk
2
)
Batch
all
all
O
(
t
2
k
)
Incremental
O
(
tk
)
O
(
t
)
O
(
k
log
t
)
Table 5.2.
Summary of time and space complexity.
9. Conclusions
This chapter surveyed techniques for dimensionality pattern discovery
across multiple streams (correlation detection and streaming dimension-
ality reduction) as well as across time within a single stream (auto-
correlation detection and filtering/compression), presenting a unified
view of these two central problems. The chapter overviewed fundamen-
tal techniques, including auto-regression, principal component analysis,
and the singular value decomposition, and shown what it takes to apply
these ideas consistently yet effectively to tackle both types of problems
on time series stream and sensor data. Furthermore, a discussion of
broadly related work in the area of time series stream mining was pre-
sented.
