Database Reference
In-Depth Information
3. Important Points
We compress a time series by selecting some of its minima and maxima,
and dropping the other points (Figure 2). The intuitive idea is to discard
minor fluctuations and keep major minima and maxima. We control the
compression rate with a parameter
R
, which is always greater than one;
an increase of
R
leads to selection of fewer points. A point
a
m
of a series
a
1
,...,a
n
is an
important minimum
if there are indices
i
and
j,
where
i ≤ m ≤ j,
such that
• a
m
is the minimum among
a
i
,...,a
j
,
and
• a
i
/a
m
≥ R
and
a
j
/a
m
≥ R.
Intuitively,
a
m
is the minimal value of some segment
a
i
,...,a
j
,
and the end-
point values of this segment are much larger than
a
m
(Figure 3). Similarly,
a
m
is an
important maximum
if there are indices
i
and
j,
where
i ≤ m ≤ j,
such that
• a
m
is the minimum among
a
i
,...,a
j
,
and
• a
m
/a
i
≥ R
and
a
m
/a
j
≥ R.
In Figure 4, we give a procedure for selecting important points, which
takes linear time and constant memory. It outputs the values and indices
of all important points, as well as the first and last point of the series.
This procedure can process new points as they arrive, without storing the
1.0
1.0
0.9
0.9
Fig. 2.
Important points for 91% compression (left) and 94% compression (right).
a
m
a
m
· R
a
m
/R
a
m
i
j
i
j
time
time
Fig. 3.
Important minimum (left) and important maximum (right).
