Discovering MOTIFs in time series with multi-dimensional index structure
Corressponding author's email:
sonnt@hcmute.edu.vnKeywords:
Time series, Multi-dimensional index, MotifAbstract
Time series motifs are frequently occurring but unknown sequences in time series database or subsequences of a longer time series. Discovering time series motifs is a crucial task in time series data mining. In this paper, we examine a search method for discovering approximate motif in time series with the support of a multidimensional index structure based on Minimum Bounding Rectangles (MBR). Our method is time and space efficient because it only saves MBRs of data in the memory and needs a single scan over the entire time series database and a few times to read the original disk data in order to confirm the results. We demonstrate the effectiveness of our approach by experimenting on real datasets from different areas. The experimental results showed that our proposed method can effectively discover time series motifs as compared to the popular method, random projection.
Downloads: 0
References
N. Beckmann, H. Kriegel, R. Schneider, B. Seeger, “The R*-tree: An efficient and robustaccess method for points and rectangles,” in Proc. of 1990 ACM SIGMOD Conf., AtlanticCity, NJ, 1990, pp. 322-331.
S. S. Cheung, and T. P. Nguyen, (2005). Mining Arbitrary-Length Repeated Patterns inTelevision Broadcast. ICIP (3) 2005: 181- 184.
B. Chiu, E. Keogh, and S. Lonardi, Probabilistic discovery of time series motifs, Proc. ofthe 9th International Conference on Knowledge Discovery and Data mining (KDD’03), pp.493–498, 2003.
N. Castro and P. Azevedo, “Multiresolution Motif Discovery in Time Series,” inProceedings of the SIAM International Conference on Data Mining (SDM 2010), Columbus,Ohio, USA, 2010, pp. 665-676.
F. Erich, G.Thiemo, N. Jiri, S. Bernhard, (2009). On-line motif detection in time serieswith SwiftMotif. In: Pattern Recognition 42(11):3015-3031. Elsevier.
P. Ferreira, P. Azevedo, C. Silva, and R. Brito, (2006). Mining approximate motifs in timeseries, in Proceedings of the 9th International Conference on Discovery Science, pp. 89-101.
A. Guttman, “R-trees: a Dynamic Index Structure for Spatial Searching,” in Proc. of theACM SIGMOD Int. Conf. on Management of Data, 1984, pp. 47-57.
J. Lin, E. Keogh, S. Lonardi, P. Patel, (2002). Finding motifs in time series. In: Proc. 2ndWorkshop on Temporal Data Mining. Edmonton, Alberta, Canada.
Li, Q., Lopez, I.F.V. and Moon, B.: Skyline Index for time series data, IEEE Trans. onKnowledge and Data Engineering, Vol. 16, No. 4 (2004)
D. Minnen, C. Isbell, I. Essa, and T. Starner, (2007). Detecting Subdimensional Motifs:An Effcient Algorithm for Generalized Multivariate Pattern Discovery, Seventh IEEEInternational Conference on Data Mining, pp 601-606.
A. Mueen, E. Keogh, Q. Zhu, S. Cash, and B. West-over, (2009). Exact Discovery ofTime Series Motifs, in the Proceedings of SIAM International Conference on Data Mining,pp. 473-484.
A. Metwally, D. Agrawal, A. El Abbadi , “Efficient Computation of Frequent and Top-kElements in Data Streams,” in Proceedings of the 10th International Conference on DatabaseTheory, 2005, pp. 398-412.
T. Oates (2002). PERUSE: An Unsupervised Algorithm for Finding Recurring Patternsin Time Series, Second IEEE International Conference on Data Mining, pp. 330.
J. Shieh and E. Keogh, “iSAX: indexing and mining terabyte sized time series,” inProceedings of the 14th ACM SIGKDD International Conference on Knowledge Discoveryand Data Mining, 2008, pp. 623-631.
Y. Tanaka, K. Iwamoto, and K. Uehara, Discovery of time-series motif from multidimensional data based on MDL principle, Machine Learning, 58(2-3):269–300, 2005.
L. Xie, (2005). Unsupervised Pattern Discovery for Multimedia Sequences. Ph.D.Thesis, Columbia University.
D. Yankov, E. Keogh, J. Medina, B. Chiu, and V. Zordan, (2007). Detecting MotifsUnder Uniform Scaling, in Proceedings of the 13th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining, pp. 844-853.
Downloads
Published
How to Cite
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright © JTE.
