On-line motif detection in time series with SwiftMotif

This article presents SwiftMotif, a novel technique for on-line motif detection in time series. With this technique, frequently occurring temporal patterns or anomalies can be discovered, for instance. The motif detection is based on a fusion of methods from two worlds: probabilistic modeling and si...

Full description

Saved in:
Bibliographic Details
Published in:Pattern recognition 2009-11, Vol.42 (11), p.3015-3031
Main Authors: Fuchs, Erich, Gruber, Thiemo, Nitschke, Jiri, Sick, Bernhard
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Information theory
Information, signal and communications theory
Motif detection
Orthogonal polynomials
Piecewise polynomial representation
Piecewise probabilistic representation
Polynomial approximation
Probabilistic modeling
Segmentation
Signal and communications theory
Signal representation. Spectral analysis
Signal, noise
SwiftMotif
Telecommunications and information theory
Temporal data mining
Time series
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This article presents SwiftMotif, a novel technique for on-line motif detection in time series. With this technique, frequently occurring temporal patterns or anomalies can be discovered, for instance. The motif detection is based on a fusion of methods from two worlds: probabilistic modeling and similarity measurement techniques are combined with extremely fast polynomial least-squares approximation techniques. A time series is segmented with a data stream segmentation method, the segments are modeled by means of normal distributions with time-dependent means and constant variances, and these models are compared using a divergence measure for probability densities. Then, using suitable clustering algorithms based on these similarity measures, motifs may be defined. The fast time series segmentation and modeling techniques then allow for an on-line detection of previously defined motifs in new time series with very low run-times. SwiftMotif is suitable for real-time applications, accounts for the uncertainty associated with the occurrence of certain motifs, e.g., due to noise, and considers local variability (i.e., uniform scaling) in the time domain. This article focuses on the mathematical foundations and the demonstration of properties of SwiftMotif—in particular accuracy and run-time—using some artificial and real benchmark time series.
ISSN:0031-3203
1873-5142
DOI:10.1016/j.patcog.2009.05.004