Database Reference
In-Depth Information
to quickly zero in on the best windows and the associated optimal local
patterns:
k
=6 and (
w
0
,W
)
∈{
(9
,
2)
,
(10
,
2)
,
(15
,
3)
}
Complexity
For a total of
L
log
W
(
t/w
0
)=
O
(log
t
) levels we
have to compute the first
k
singular values and vectors of
X
(
w
0
,l
)
≈
∈
t/
(
w
0
W
l
)
×Wk
,for
l
=1
,
2
,...
. A batch SVD algorithm requires time
R
O
k
w
0
W
l
,whichis
O
W
2
k
2
t
W
l
since
k<w
0
. Summing over
(
Wk
)
2
t
·
·
l
=1
,...,L
,weget
O
(
W
2
k
2
t
). Finally, for
l
= 0, we need
O
k
w
0
=
O
(
kw
0
t
). Thus, the total complexity is
O
(
W
2
k
2
t
+
kw
0
t
). Since
W
and
w
0
are fixed, we finally have the following
Lemma 5.13 (Batch hierarchical complexity)
The total time for
the hierarchical approach is
O
(
k
2
t
)
, i.e., linear with respect to the time
series length.
This is a big improvement over the
O
(
t
3
k
) time of the non-hierarchical
approach. However, we still need to buffer all the points. We address
this problem in the next section.
w
0
t
·
8.3 Streaming Computation
In this section we explain how to perform the necessary computations
in an incremental, streaming fashion. We designed our models precisely
to allow this step. The main idea is that we recursively invoke only
one iteration of each loop in IncrementalSVD (for LocalPattern)
and in Hierarchical, as soon as the necessary number of points has
arrived. Subsequently, we can discard these points and proceed with the
next non-overlapping window.
Modifying LocalPattern
We buffer consecutive points of
x
(or, in
general, rows of
X
) until we accumulate
w
of them, forming one row
of
X
(
w
)
. At that point, we can perform one iteration of the outer loop
in IncrementalSVD to update all
k
local patterns. Then, we can
discard the
w
points (or rows) and proceed with the next
w
. Also, since
on higher levels the number of points for SVD may be small and close to
k
, we may choose to initially buffer just the first
k
rows of
X
(
w
)
and use
them to bootstrap the SVD estimates, which we subsequently update as
described.
Modifying Hierarchical
For level
l
= 0 we use the modified Local-
Pattern on the original series, as above. However, we also store the
k
projections onto the level-0 patterns. We buffer
W
consecutive sets of
