Database Reference
In-Depth Information
imating functions. APCA [8] and other similar approaches approximate
the time series with piecewise constant or linear functions. DAWA [28]
combines the DCT and DWT. However, all these approaches focus on
compressing the time series for indexing purposes, and not on pattern
discovery. AWSOM [43] first applies the wavelet transform. As the au-
thors observe, just a few wavelet coecients do not capture all patterns
in practice, so AWSOM subsequently captures trends by fitting a linear
auto-regressive model at each time scale.
The seminal work of [12] for rule discovery in time series is based
on sequential patterns extracted after a discretization step. Other work
has also focused on finding representative trends [32]. A representative
trend is a subsequence of the time series that has the smallest sum of
distances from all other subsequences of the same length. The proposed
method employs random projections and FFT to quickly compute the
sum of distances. This does not apply directly to streams and it is not
easy to extend, since each section has to be compared to all others. Our
approach is complementary and could conceivably be used in place of
the FFT in this setting. Related to representative trends are motifs
[45, 10]. Intuitively, these are frequently repeated subsequences, i.e.,
subsequences of a given length which match (in terms of some distance
and a given distance threshold) a large number of other subsequences
of the same time series. More recently, vector quantization has been
used for time series compression [38, 37]. The first focuses on finding
good-quality and intuitive distance measures for indexing and similarity
search and is not applicable to streams, while the second focuses on
reducing power consumption for wireless sensors. Finally, other work
on stream mining includes approaches for periodicity [18] and periodic
patterns [17] discovery.
More recently, [48] have studied how eciently store time series,
while allowing computation of several quantities (e.g., correlations, his-
tograms) directly in the compressed domain, by leveraging multi-scale
analysis to obtain sparse time/frequency representations of time series.
The work of [47] considers the problem of discovering patterns on a single
time series by clustering series from one time series stream, and proposes
an MDL-based framework for eciently discovering good clusters.
Approaches for regression on time series and streams include [9] and
amnesic functions [42]. Both of these estimate the best fit of a given
function (e.g., linear or low-degree polynomial), they work by merging
the estimated fit on consecutive windows and can incorporate exponential-
size time windows placing less emphasis on the past. However, both of
these approaches employ a fixed, given set of approximating functions.
Search WWH ::




Custom Search