An efficient implementation of EMD algorithm for motif discovery in time series data

Duong Tuan Anh and Nguyen Van Nhat

International Journal of Data Mining, Modelling and Management, 2016, vol. 8, issue 2, 180-194

Abstract: The extended motif discovery (EMD) algorithm, developed by Tanaka et al. (2005), is a well-known time series motif discovery algorithm which is based on minimum description length principle. One unique feature of the EMD algorithm is that it can determine the suitable length of the motif and hence does not require the length of the motif as a parameter supplied by user. Another interesting feature of the EMD is the lengths of each instances of a motif can be a bit different from each other and hence Tanaka et al. suggested that dynamic time warping (DTW) distance should be used to calculate the distances between the motif instances in this case. Due to the second feature, the EMD algorithm leads to a high computational complexity and is not easy to implement in practice. In this paper, we present an efficient implementation of the EMD algorithm in which we apply homothetic transformation to convert all pattern instances of different lengths into the same length so that we can easily calculate Euclidean distances between them. This modification accelerates the execution of the EMD remarkably and makes it easier to implement. Experimental results on seven real world time series datasets demonstrate the effectiveness of our EMD implementation method in time series motif discovery.

Keywords: time series; extended motif discovery; EMD algorithm; homothetic transformation; Euclidean distances. (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=77159 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijdmmm:v:8:y:2016:i:2:p:180-194

Access Statistics for this article

More articles in International Journal of Data Mining, Modelling and Management from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().