Multiresolution Motif Discovery in Time Series

Supporting web page of our paper:

Nuno Castro and Paulo Azevedo, Multiresolution Motif Discovery in Time Series,
in Proceedings of the SIAM International Conference on Data Mining (SDM 2010), Columbus, Ohio, USA. SIAM, 2010, pp. 665-676. [pdf] [slides]
[Free Java source code] [DBLP] [Scholar] [BibTeX]

[iMotifs - a MrMotif GUI] [You may also be interested in finding Statistically Significant Motifs.]

A time series motif is a frequent pattern in time series data, i.e. a repetition of a particular subsection of the series.

Figure 1: Example of a motif with 3 repetitions (instances) in the context of EEG data from [1].

We introduce MrMotif, a scalable algorithm to discover motifs in time series at several resolutions.
MrMotif is:

Fast - executes in linear time, by using one single sequential disk scan over the database and constant access time structures;
Space-efficient - it uses a small (and adjustable) amount of memory; use a well studied space saving algorithm [3];
Intuitive - outputs the most frequent patterns of the database in an intuitive way;
Robust to noise - it maintains the quality of the retrieved patterns in noisy data;
Easy to use - a small number of parameters need be configured;
Straightforward - algorithm is simple to understand and implement;
Reproducible - we provide the source code and datasets.

MrMotif is based on the state of the art iSAX [2] time series representation. For an explanation of time series similarity, repetition counting and iSAX check this page.

References

[1] Yankov, D., Keogh, E., Medina, J., Chiu, B., Zordan, V., Detecting Motifs Under Uniform Scaling,
in Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2007), pp. 844-853.

[2] Shieh, J. and Keogh, E., iSAX: indexing and mining terabyte sized time series,
in Proceedings of the 14th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining (2008), pp. 623-631.

[3] Metwally, A., Agrawal, D., and Abbadi, A., Efficient Computation of Frequent and Top-k Elements in Data Streams,
in Proceedings of the 10th International Conference on Database Theory (2005), pp. 398-412.

[4] Mueen, A., Keogh, E., Zhu, Q., Cash, S., and West-over, B., Exact Discovery of Time Series Motifs,
in Proceedings of SIAM International Conference on Data Mining (2009), pp. 473-484.