Database Reference
In-Depth Information
(a)
(b)
Fig. 1. Two time series and their piecewise linear representation. (a) Space Shuttle
Telemetry. (b) Electrocardiogram (ECG).
representations of time series have been proposed, including Fourier Trans-
forms [Agrawal
et al.
(1993), Keogh
et al.
(2000)], Wavelets [Chan and Fu
(1999)], Symbolic Mappings [Agrawal
et al.
(1995), Das
et al.
(1998), Perng
et al.
(2000)] and Piecewise Linear Representation (PLR). In this work,
we confine our attention to PLR, perhaps the most frequently used repre-
sentation [Ge and Smyth (2001), Last
et al.
(2001), Hunter and McIntosh
(1999), Koski
et al.
(1995), Keogh and Pazzani (1998), Keogh and Pazzani
(1999), Keogh and Smyth (1997), Lavrenko
et al.
(2000), Li
et al.
(1998),
Osaki
et al.
(1999), Park
et al.
(2001), Park
et al.
(1999), Qu
et al.
(1998),
Shatkay (1995), Shatkay and Zdonik (1996), Vullings
et al.
(1997), Wang
and Wang (2000)].
Intuitively, Piecewise Linear Representation refers to the approximation
of a time series
, with K straight lines (hereafter known as
segments). Figure 1 contains two examples. Because K is typically much
smaller that
T
, of length
n
, this representation makes the storage, transmission and
computation of the data more ecient. Specifically, in the context of data
mining, the piecewise linear representation has been used to:
•
n
Support fast exact similarly search [Keogh
et al.
(2000)].
•
Support novel distance measures for time series, including “fuzzy queries”
[Shatkay (1995), Shatkay and Zdonik (1996)], weighted queries [Keogh
and Pazzani (1998)], multiresolution queries [Wang and Wang (2000),
Li
et al.
(1998)], dynamic time warping [Park
et al.
(1999)] and relevance
feedback [Keogh and Pazzani (1999)].
•
Support concurrent mining of text and time series [Lavrenko
et al.
(2000)].
•
Support novel clustering and classification algorithms [Keogh and
Pazzani (1998)].
•
Support change point detection [Sugiura and Ogden (1994), Ge and
Smyth (2001)].