Abstract
Motif discovery is the problem of finding unknown patterns that appear frequently in real valued timeseries. Several approaches have been proposed to solve this problem with no a-priori knowledge of the timeseries or motif characteristics. MK algorithm is the de facto standard exact motif discovery algorithm but it can discover a single motif of a known length. In this paper, we argue that it is not trivial to extend this algorithm to handle multiple motifs of variable lengths when constraints of maximum overlap are to be satisfied which is the case in many real world applications. The paper proposes an extension of the MK algorithm called MK++ to handle these conditions. We compare this extensions with a recently proposed approximate solution and show that it is not only guaranteed to find the exact top pair-motifs but that it is also faster. The proposed algorithm is then applied to several real-world time series.
The work reported in this paper is partially supported by JSPS Post-Doc Fellowship and Grant-In-Aid Programs of the Japanese Society for Promotion of Science.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Buhler, J., Tompa, M.: Finding motifs using random projections. In: 5th Internatinal Conference on Computational Biology, pp. 69–76 (2001)
Catalano, J., Armstrong, T., Oates, T.: Discovering patterns in real-valued time series. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) PKDD 2006. LNCS (LNAI), vol. 4213, pp. 462–469. Springer, Heidelberg (2006)
Chiu, B., Keogh, E., Lonardi, S.: Probabilistic discovery of time series motifs. In: ACM SIGKDD KDD, pp. 493–498 (2003)
CMU: Cmu motion capture dataset, http://mocap.cs.cmu.edu
Keogh, E., Lin, J., Fu, A.: Hot sax: efficiently finding the most unusual time series subsequence. In: Fifth IEEE ICDM, pp. 8–17 (2005)
Lin, J., Keogh, E., Lonardi, S., Patel, P.: Finding motifs in time series. In: The 2nd Workshop on Temporal Data Mining, at the 8th ACM SIGKDD International, pp. 53–68 (2002)
Minnen, D., Starner, T., Essa, I.A., Isbell Jr., C.L.: Improving activity discovery with automatic neighborhood estimation. In: IJCAI, vol. 7, pp. 2814–2819 (2007)
Mohammad, Y., Nishida, T.: Learning interaction protocols using augmented baysian networks applied to guided navigation. In: IEEE IROS, pp. 4119–4126 (2010)
Mohammad, Y., Nishida, T.: Constrained motif discovery in time series. New Generation Computing 27(4), 319–346 (2009)
Mohammad, Y., Nishida, T.: Unsupervised discovery of basic human actions from activity recording datasets. In: IEEE/SICE SII, pp. 402–409 (2012)
Mohammad, Y., Ohmoto, Y., Nishida, T.: G-SteX: Greedy stem extension for free-length constrained motif discovery. In: Jiang, H., Ding, W., Ali, M., Wu, X. (eds.) IEA/AIE 2012. LNCS, vol. 7345, pp. 417–426. Springer, Heidelberg (2012)
Mueen, A., Keogh, E.J., Zhu, Q., Cash, S., Westover, M.B.: Exact discovery of time series motifs. In: SDM, pp. 473–484 (2009)
Mueen, A.: Enumeration of Time Series Motifs of All Lengths. In: IEEE ICDM (2013)
Kipp, M.: Anvil – A Generic Annotation Tool for Multimodal Dialogue. In: Eurospeech, pp. 1367–1370 (2001)
Mohammad, Y., Nishida, T.: Approximately Recurring Motif Discovery Using Shift Density Estimation. In: Ali, M., Bosse, T., Hindriks, K.V., Hoogendoorn, M., Jonker, C.M., Treur, J. (eds.) IEA/AIE 2013. LNCS, vol. 7906, pp. 141–150. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Mohammad, Y., Nishida, T. (2014). Exact Discovery of Length-Range Motifs. In: Nguyen, N.T., Attachoo, B., Trawiński, B., Somboonviwat, K. (eds) Intelligent Information and Database Systems. ACIIDS 2014. Lecture Notes in Computer Science(), vol 8398. Springer, Cham. https://doi.org/10.1007/978-3-319-05458-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-05458-2_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-05457-5
Online ISBN: 978-3-319-05458-2
eBook Packages: Computer ScienceComputer Science (R0)