A SURVEY OF RECENT METHODS FOR EFFICIENT RETRIEVAL OF SIMILAR TIME SEQUENCES - Data Mining in Time Series Databases - page 33

3.3. Piecewise Constant Approximation
An approach independently introduced by Yi and Faloutsos (2000) and
Keogh et al. (2001b), Keogh and Pazzani (2000) is to divide each sequence
into

segments of equal length, and to use the average value of each seg-
ment as a coordinate of a

k

-dimensional signature vector. Keogh et al. call
the method Piecewise Constant Approximation , or PCA. This deceptively
simple dimensionality reduction technique has several advantages [Keogh
et al . (2001b)]: The transform itself is faster than most other transforms,
it is easy to understand and implement, it supports more flexible distance
measures than Euclidean distance, and the index can be built in linear time.
Figure 8 shows an approximated time sequence, reconstructed from a
ten-dimensional PCA signature.
Yi and Faloutsos (2000) also show that this signature can be used with
arbitrary

k

L p norms without changing the index structure, which is some-
thing no previous method [such as Agrawal et al. (1993; 1995), Faloutsos
et al. (1994; 1997), Rafiei and Mendelzon (1997), or Yi et al. (1998)] could
accomplish. This means that the distance measure may be specified by the
user. Preprocessing to make the index more robust in the face of such trans-
formations as offset translation , amplitude scaling ,and time scaling can also
be performed.
Keogh et al . demonstrate that the representation can also be used with
the so-called weighted Euclidean distance , where each part of the sequence
has a different weight.
Empirically, the PCA methods seem promising: Yi and Faloutsos
demonstrate up to a ten times speedup over methods based on the discrete
wavelet transform. Keogh et al. do not achieve similar speedups, but point
to the fact that the structure allows for more flexible distance measures
than many of the competing methods.
Keogh et al . (2001a) later propose an improved version of the PCA, the
so-called Adaptive Piecewise Constant Approximation , or APCA. This is

Fig. 8. A sequence reconstructed from a PCA signature.