Please wait a minute...
Front. Inform. Technol. Electron. Eng.  2011, Vol. 12 Issue (12): 1000-1009    DOI: 10.1631/jzus.C1100037
    
Comprehensive and efficient discovery of time series motifs
Lian-hua Chi*,1, He-hua Chi2, Yu-cai Feng1, Shu-liang Wang3, Zhong-sheng Cao1
1 School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China 2 State Key Laboratory of Software Engineering, Computer School, Wuhan University, Wuhan 430079, China 3 International School of Software, Wuhan University, Wuhan 430079, China
Download:   PDF(832KB)
Export: BibTeX | EndNote (RIS)      

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.

Key wordsTime series motifs      Definition of K-motifs      Optimized matrix structure      Fast pruning method     
Received: 16 February 2011      Published: 30 November 2011
CLC:  TP391.4  
Cite this article:

Lian-hua Chi, He-hua Chi, Yu-cai Feng, Shu-liang Wang, Zhong-sheng Cao. Comprehensive and efficient discovery of time series motifs. Front. Inform. Technol. Electron. Eng., 2011, 12(12): 1000-1009.

URL:

http://www.zjujournals.com/xueshu/fitee/10.1631/jzus.C1100037     OR     http://www.zjujournals.com/xueshu/fitee/Y2011/V12/I12/1000


Comprehensive and efficient discovery of time series motifs

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.

关键词: Time series motifs,  Definition of K-motifs,  Optimized matrix structure,  Fast pruning method 
[1] Yuan-ping Nie, Yi Han, Jiu-ming Huang, Bo Jiao, Ai-ping Li. Attention-based encoder-decoder model for answer selection in question answering[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 535-544.
[2] Rong-Feng Zhang , Ting Deng , Gui-Hong Wang , Jing-Lun Shi , Quan-Sheng Guan . A robust object tracking framework based on a reliable point assignment algorithm[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 545-558.
[3] Le-kui Zhou, Si-liang Tang, Jun Xiao, Fei Wu, Yue-ting Zhuang. Disambiguating named entities with deep supervised learning via crowd labels[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 97-106.
[4] Yue-ting Zhuang, Fei Wu, Chun Chen, Yun-he Pan. Challenges and opportunities: from big data to knowledge in AI 2.0[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 3-14.
[5] M. F. Kazemi, M. A. Pourmina, A. H. Mazinan. Level-direction decomposition analysis with a focus on image watermarking framework[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(11): 1199-1217.
[6] Guang-hui Song, Xiao-gang Jin, Gen-lang Chen, Yan Nie. Two-level hierarchical feature learning for image classification[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(9): 897-906.
[7] Jia-yin Song, Wen-long Song, Jian-ping Huang, Liang-kuan Zhu. Segmentation and focus-point location based on boundary analysis in forest canopy hemispherical photography[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(8): 741-749.
[8] Gao-li Sang, Hu Chen, Ge Huang, Qi-jun Zhao. Unseen head pose prediction using dense multivariate label distribution[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(6): 516-526.
[9] Xi-chuan Zhou, Fang Tang, Qin Li, Sheng-dong Hu, Guo-jun Li, Yun-jian Jia, Xin-ke Li, Yu-jie Feng. Global influenza surveillance with Laplacian multidimensional scaling[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(5): 413-421.
[10] Chu-hua Huang, Dong-ming Lu, Chang-yu Diao. A multiscale-contour-based interpolation framework for generating a time-varying quasi-dense point cloud sequence[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(5): 422-434.
[11] Xiao-hu Ma, Meng Yang, Zhao Zhang. Local uncorrelated local discriminant embedding for face recognition[J]. Front. Inform. Technol. Electron. Eng., 2016, 17(3): 212-223.
[12] Fu-xiang Lu, Jun Huang. Beyond bag of latent topics: spatial pyramid matching for scene category recognition[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(10): 817-828.
[13] Yu Liu, Bo Zhu. Deformable image registration with geometric changes[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(10): 829-837.
[14] Xun Liu, Yin Zhang, San-yuan Zhang, Ying Wang, Zhong-yan Liang, Xiu-zi Ye. Detection of engineering vehicles in high-resolution monitoring images[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(5): 346-357.
[15] Xiao-fang Huang, Shou-qian Sun, Ke-jun Zhang, Tian-ning Xu, Jian-feng Wu, Bin Zhu. A method of shadow puppet figure modeling and animation[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(5): 367-379.