Database Reference
In-Depth Information
(i.e. the L
norm between the line and the data). As before, we have
kept our descriptions of the algorithms general enough to encompass any
error measure. In particular, the pseudocode function
calculate error(T)
can be imagined as using any sum of squares, furthest point, or any other
measure.
∞
2.1.
The Sliding Window Algorithm
The Sliding Window algorithm works by anchoring the left point of a poten-
tial segment at the first data point of a time series, then attempting to
approximate the data to the right with increasing longer segments. At some
point
, the error for the potential segment is greater than the user-specified
threshold, so the subsequence from the anchor to
i
i −
1 is transformed into
a segment. The anchor is moved to location
, and the process repeats until
the entire time series has been transformed into a piecewise linear approx-
imation. The pseudocode for the algorithm is shown in Table 2.
The Sliding Window algorithm is attractive because of its great sim-
plicity, intuitiveness and particularly the fact that it is an online algorithm.
Several variations and optimizations of the basic algorithm have been pro-
posed. Koski
et al.
noted that on ECG data it is possible to speed up the
algorithm by incrementing the variable
i
i
by “leaps of length
k
” instead of
1. For
= 15 (at 400 Hz), the algorithm is 15 times faster with little effect
on the output accuracy [Koski
et al.
(1995)].
Depending on the error measure used, there may be other optimizations
possible. Vullings
et al.
noted that since the residual error is monotonically
non-decreasing with the addition of more data points, one does not have
to test every value of
k
from 2 to the final chosen value [Vullings
et al.
(1997)]. They suggest initially setting
i
is the mean length
of the previous segments. If the guess was pessimistic (the measured error
i
to
s
,where
s
Table 2. The generic Sliding Window algorithm.
Algorithm
Algorithm Seg TS = Sliding Window(T, max error)
anchor = 1;
while not finished segmenting time series
while not finished segmenting time series
while not finished segmenting time series
i=2;
while
while
while calculate error(T[anchor: anchor+i])<maxerror
i=i+1;
end;
end;
end;
Seg TS = concat(Seg TS, create segment(T[anchor: anchor
+ (i - 1)]);anchor = anchor + i;
end;
