Database Reference
In-Depth Information
IMPORTANT-POINTS—Top-level function for finding important points.
The input is a time series
a
1
,...,a
n
; the output is the
values and indices of the selected important points.
output
(
a
1
,
1)
i
= FIND-FIRST
if
i<n
and
a
i
>a
1
then
i
= FIND-MAXIMUM(
i
)
while
i<n
do
i
= FIND-MINIMUM(
i
)
i
= FIND-MAXIMUM(
i
)
output
(
a
n
,n
)
FIND-FIRST—Find the first important point.
iMin
=1;
iMax
=1;
i
=2
while
i<n
and
a
i
/a
iMin
<R
and
a
iMax
/a
i
<R
do
if
a
i
<a
iMin
then
iMin
=
i
if
a
i
>a
iMax
then
iMax
=
i
i
=
i
+1
if
iMin < iMax
then output
(
a
iMin,
iMin
)
else output
(
a
iMax,
iMax
)
return
i
FIND-MINIMUM(
i
)—Find the first important maximum after the
i
th point.
iMin
=
i
while
i<n
and
a
i
/a
iMin
<R
do
if
a
i
<a
iMin
then
iMin
=
i
i
=
i
+1
if
i<n
or
a
iMin
<a
i
then output
(
a
i
Min, iMin
)
return
i
FIND-MAXIMUM(
i
)—Find the first important maximum after the
i
th point.
iMax
=
i
while
i<n
and
a
iMax
/a
i
<R
do
if
a
i
>a
iMax
then
iMax
=
i
i
=
i
+1
if
i<n
or
a
iMax
>a
i
then output
(
a
iMax
,iMax
)
return
i
Fig. 4. Compression procedure. We process a series
a
1
,...,a
n
and use a global variable
n
to represent its size. The procedure outputs the values and indices of the selected points.
original series; for example, it can compress a live electroencephalogram
without waiting until the end of the data collection. We have implemented
it in Visual Basic 6 and tested on a 300-MHz PC; for an
n
-point series, the
compression time is 14
· n
microseconds.
