SEGMENTING TIME SERIES: A SURVEY AND NOVEL APPROACH - Data Mining in Time Series Databases - page 16

Bottom-Up is applied to the data in the buffer and the leftmost segment
is reported. The data corresponding to the reported segment is removed
from the buffer and more datapoints are read in. The number of datapoints
read in depends on the structure of the incoming data. This process is per-
formed by the Best Line function, which is basically just classic Sliding
Windows. These points are incorporated into the buffer and Bottom-Up is
applied again. This process of applying Bottom-Up to the buffer, report-
ing the leftmost segment, and reading in the next “best fit” subsequence is
repeated as long as data arrives (potentially forever).
The intuition behind the algorithm is this. The Best Line function
finds data corresponding to a single segment using the (relatively poor)
Sliding Windows and gives it to the buffer. As the data moves through the
buffer the (relatively good) Bottom-Up algorithm is given a chance to refine
the segmentation, because it has a “semi-global” view of the data. By the
time the data is ejected from the buffer, the segmentation breakpoints are
usually the same as the ones the batch version of Bottom-Up would have
chosen. Table 6 shows the pseudo code for the algorithm.

Table 6. The SWAB (Sliding Window and Bottom-up) algorithm.

Algorithm

Algorithm Algorithm Seg TS = SWAB(max error, seg num) // seg num is a small integer,

i.e.5or6
read in w number of data points

read in w number of data points

read in w number of data points // Enough to approximate
lower bound=w/2; //segnum of segments.
upper bound=2*w;
while

while

while data at input
T = Bottom Up(w, max error) // Call the Bottom-Up algorithm.

Seg TS = CONCAT(SEG TS, T(1));
w = TAKEOUT(w, w ); // Deletes w points in T(1) from w.
iiif data at input // Add w points from BEST LINE() to w.
w = CONCAT(w, BEST LINE(max error));
{ check upper and lower bound, adjust if necessary }
else else else // flush approximated segments from buffer.

Seg TS = CONCAT(SEG TS, (T - T(1)))
end; end;

end; end;

Function Function Function S = BEST LINE(max error) // returns S points to approximate.

≤

while while error max error // next potential segment.

read in one additional data point, d, into S
S = CONCAT(S, d);
error = approx segment(S);
end while; end while; end while;

return return return S;