Full Text:   <1647>

CLC number: TP391.4

On-line Access: 2011-11-30

Received: 2011-02-16

Revision Accepted: 2011-06-15

Crosschecked: 2011-11-04

Cited: 3

Clicked: 4229

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2011 Vol.12 No.12 P.1000-1009

http://doi.org/10.1631/jzus.C1100037


Comprehensive and efficient discovery of time series motifs


Author(s):  Lian-hua Chi, He-hua Chi, Yu-cai Feng, Shu-liang Wang, Zhong-sheng Cao

Affiliation(s):  School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China, State Key Laboratory of Software Engineering, Computer School, Wuhan University, Wuhan 430079, China, International School of Software, Wuhan University, Wuhan 430079, China

Corresponding email(s):   lianhua1221@gmail.com

Key Words:  Time series motifs, Definition of K-motifs, Optimized matrix structure, Fast pruning method


Lian-hua Chi, He-hua Chi, Yu-cai Feng, Shu-liang Wang, Zhong-sheng Cao. Comprehensive and efficient discovery of time series motifs[J]. Journal of Zhejiang University Science C, 2011, 12(12): 1000-1009.

@article{title="Comprehensive and efficient discovery of time series motifs",
author="Lian-hua Chi, He-hua Chi, Yu-cai Feng, Shu-liang Wang, Zhong-sheng Cao",
journal="Journal of Zhejiang University Science C",
volume="12",
number="12",
pages="1000-1009",
year="2011",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1100037"
}

%0 Journal Article
%T Comprehensive and efficient discovery of time series motifs
%A Lian-hua Chi
%A He-hua Chi
%A Yu-cai Feng
%A Shu-liang Wang
%A Zhong-sheng Cao
%J Journal of Zhejiang University SCIENCE C
%V 12
%N 12
%P 1000-1009
%@ 1869-1951
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1100037

TY - JOUR
T1 - Comprehensive and efficient discovery of time series motifs
A1 - Lian-hua Chi
A1 - He-hua Chi
A1 - Yu-cai Feng
A1 - Shu-liang Wang
A1 - Zhong-sheng Cao
J0 - Journal of Zhejiang University Science C
VL - 12
IS - 12
SP - 1000
EP - 1009
%@ 1869-1951
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1100037


Abstract: 
time series motifs are previously unknown, frequently occurring patterns in time series or approximately repeated subsequences that are very similar to each other. There are two issues in time series motifs discovery, the deficiency of the definition of K-motifs given by Lin et al. (2002) and the large computation time for extracting motifs. In this paper, we propose a relatively comprehensive definition of K-motifs to obtain more valuable motifs. To minimize the computation time as much as possible, we extend the triangular inequality pruning method to avoid unnecessary operations and calculations, and propose an optimized matrix structure to produce the candidate motifs almost immediately. Results of two experiments on three time series datasets show that our motifs discovery algorithm is feasible and efficient.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Abe, H., Ohsaki, M., Yokoi, H., Yamaguchi, T., 2005. Implementing an integrated time-series data mining environment based on temporal pattern extraction methods: a case study of an interferon therapy risk mining for chronic hepatitis. LNCS, 4012:425-435.

[2]André-Jönsson, H., Badal, D.Z., 1997. Using Signature Files for Querying Time-Series Data. Practice of Knowledge Discovery in Databases, 1263:211-220.

[3]Beaudoin, P., Coros, S., van~de Panne, M., Poulin, P., 2008. Motion-Motif Graphs. Symp. on Computer Animation, p.117-126.

[4]Chiu, B.Y., Keogh, E.J., Lonardi, S., 2003. Probabilistic Discovery of Time Series Motifs. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.493-498.

[5]Ding, H., Trajcevski, G., Scheuermann, P., Wang, X.Y., Keogh, E.J., 2008. Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures. Proc. Int. Conf. on Very Large Data Bases, 1(2):1542-1552.

[6]Ferreira, P.G., Azevedo, P.J., Silva, C.G., Brito, R.M.M., 2006. Mining approximate motifs in time series. Discov. Sci., 4265:89-101.

[7]Guyet, T., Garbay, C., Dojat, M., 2007. Knowledge construction from time series data using a collaborative exploration system. J. Biomed. Inform., 40(6):672-687.

[8]Hegland, M., Clarke, W., Kahn, M., 2001. Mining the Macho dataset. Comput. Phys. Commun., 142(1-3):22-28.

[9]Lin, J., Keogh, E., Lonardi, S., Patel, P., 2002. Finding Motifs in Time Series. 2nd Workshop on Temporal Data Mining at the 8th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.53-68.

[10]Mueen, A., Keogh, E.J., Zhu, Q., Cash, S., Westover, M.B., 2009. Exact Discovery of Time Series Motifs. Society for Industrial and Applied Mathematics Conf. on Data Mining, p.473-484.

[11]Tanaka, Y., Iwamoto, K., Uehara, K., 2005. Discovery of time-series motif from multi-dimensional data based on MDL principle. Mach. Learn., 58(2-3):269-300.

[12]Ueno, K., Xi, X.P., Keogh, E.J., Lee, D.J., 2006. Anytime Classification Using the Nearest Neighbor Algorithm with Applications to Stream Mining. IEEE Int. Conf. on Data Mining, p.623-632.

[13]Xu, X.K., Zhang, J., Small, M., 2008. Superfamily phenomena and motifs of networks induced from time series. PNAS, 105(50):19601-19605.

[14]Yi, B.K., Faloutsos, C., 2000. Fast Time Sequence Indexing for Arbitrary Lp Norms. Int. Conf. on Very Large Data Bases, p.385-394.

[15]Zhang, J., Small, M., 2006. Complex network from pseudoperiodic time series: topology versus dynamics. Phys. Rev. Lett., 96:238701.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE