SMM: Leveraging Metadata for Contextually Salient Multi-Variate Motif Discovery
Source abstract
Abstract
A common challenge in multimedia data understanding is the unsupervised discovery of recurring patterns, or motifs, in time series data. The discovery of motifs in uni-variate time series is a well studied problem and, while being a relatively new area of research, there are also several proposals for multi-variate motif discovery. Unfortunately, motif search among multiple variates is an expensive process, as the potential number of sub-spaces in which a pattern can occur increases exponentially with the number of variates. Consequently, many multi-variate motif search algorithms make simplifying assumptions, such as searching for motifs across all variates individually, assuming that the motifs are of the same length, or that they occur on a fixed subset of variates. In this paper, we are interested in addressing a relatively broad form of multi-variate motif detection, which seeks frequently occurring patterns (of possibly differing lengths) in sub-spaces of a multi-variate time series. In particular, we aim to leverage contextual information to help select contextually salient patterns and identify the most frequent patterns among all. Based on these goals, we first introduce the contextually salient multi-variate motif (CS-motif) discovery problem and then propose a salient multi-variate motif (SMM) algorithm that, unlike existing methods, is able to seek a broad range of patterns in multi-variate time series.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Time Series Analysis and Forecasting · Music and Audio Processing · Data Management and Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Computer Science Department, University of Torino, 10149 Torino, Italy
School of Computing and Augmented Intelligence (SCAI), Arizona State University, Tempe, AZ 85287-8809, USA
Funding
National Science Foundation · European Union
References (37)
Show source-provided references
1. Multimedia search reranking: A literature survey10.1145/2536798 ↗
2. Yang, X., Zhang, C., and Tian, Y. (November, January 29). Recognizing actions using depth motion maps-based histograms of oriented gradients. Proceedings of the 20th ACM International Conference on Multimedia, Nara, Japan.
3. A survey of vision-based methods for action representation, segmentation and recognition10.1016/j.cviu.2010.10.002 ↗
4. Scovanner, P., Ali, S., and Shah, M. (2007, January 25–29). A 3-dimensional sift descriptor and its application to action recognition. Proceedings of the 15th ACM International Conference on Multimedia, Augsburg, Germany.10.1145/1291233.1291311 ↗
5. Survey on time series motif discovery10.1002/widm.1199 ↗
6. Discovery of time-series motif from multi-dimensional data based on MDL principle10.1007/s10994-005-5829-2 ↗
7. Discovering Multidimensional Motifs in Physiological Signals for Personalized Healthcare10.1109/JSTSP.2016.2543679 ↗
8. Balasubramanian, A., and Prabhakaran, B. (2013, January 11). Flexible exploration and visualization of motifs in biomedical sensor data. Proceedings of the Workshop on Data Mining for Healthcare (DMH), in Conjunction with ACM KDD, Chicago, IL, USA.
9. Yeh, C.C.M., Kavantzas, N., and Keogh, E. (2017, January 18–21). Matrix Profile VI: Meaningful Multidimensional Motif Discovery. Proceedings of the 2017 IEEE International Conference on Data Mining (ICDM), New Orleans, LA, USA.10.1109/ICDM.2017.66 ↗
10. Lab, C.G. (2021, October 10). Motion Capture Database. Available online: http://mocap.cs.cmu.edu/.
11. Buhler, J., and Tompa, M. (2001, January 22–25). Finding motifs using random projections. Proceedings of the Fifth Annual International Conference on Computational Biology, ACM, RECOMB ’01, Montreal, QC, Canada.10.1145/369133.369172 ↗
12. Patel, P., Keogh, E., Lin, J., and Lonardi, S. (2002, January 9–12). Mining Motifs in Massive Time Series Databases. Proceedings of IEEE International Conference on Data Mining (ICDM’02), Maebashi City, Japan.10.1109/ICDM.2002.1183925 ↗
13. Keogh, E., Lin, J., and Truppel, W. (2003, January 19–22). Clustering of Time Series Subsequences is Meaningless: Implications for Previous and Future Research. Proceedings of the Third IEEE International Conference on Data Mining, ICDM ’03, Melbourne, FL, USA.
14. A novel pattern extraction method for time series classification10.1007/s11081-008-9056-0 ↗
15. Time-series data mining10.1145/2379776.2379788 ↗
16. Discovering original motifs with different lengths from time series10.1016/j.knosys.2008.03.022 ↗
17. Mining Approximate Motifs in Time Series10.1007/11893318_12 ↗
18. Lin, J., Keogh, E., Lonardi, S., and Chiu, B. (2003, January 13). A symbolic representation of time series, with implications for streaming algorithms. Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, San Diego, CA, USA.10.1145/882082.882086 ↗
19. Chiu, B., Keogh, E., and Lonardi, S. (2003, January 24–27). Probabilistic discovery of time series motifs. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, Washington, DC, USA.10.1145/956804.956808 ↗
20. Yankov, D., Keogh, E., Medina, J., Chiu, B., and Zordan, V. (2007, January 12–15). Detecting time series motifs under uniform scaling. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’07, San Jose, CA, USA.10.1145/1281192.1281282 ↗
21. Castro, N., and Azevedo, P. (May, January 29). Multiresolution Motif Discovery in Time Series. Proceedings of the SIAM International Conference on Data Mining, Columbus, OH, USA.
22. Mueen, A., Keogh, E.J., Zhu, Q., Cash, S., and Westover, M.B. (May, January 30). Exact Discovery of Time Series Motifs. Proceedings of the SIAM International Conference on Data Mining, Sparks, NV, USA.
23. Lam, H.T., Calders, T., and Pham, N. (2011, January 28–30). Online Discovery of Top-k Similar Motifs in Time Series Data. Proceedings of the SIAM International Conference on Data Mining, Mesa, AZ, USA.10.1137/1.9781611972818.86 ↗
24. Constrained Motif Discovery in Time Series10.1007/s00354-009-0068-x ↗
25. Yeh, C.C.M., Zhu, Y., Ulanova, L., Begum, N., Ding, Y., Dau, H.A., Silva, D.F., Mueen, A., and Keogh, E. (2016, January 12–15). Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets. Proceedings of the 2016 IEEE 16th International Conference on Data Mining (ICDM), Barcelona, Spain.10.1109/ICDM.2016.0179 ↗
26. Grünwald, P.D., Myung, I.J., and Pitt, M.A. (2005). Advances in Minimum Description Length: Theory and Applications, MIT Press.10.7551/mitpress/1114.001.0001 ↗
27. Vahdatpour, A., Amini, N., and Sarrafzadeh, M. (2009, January 11–17). Toward Unsupervised Activity Discovery Using Multi-Dimensional Motif Detection in Time Series. Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, CA, USA.
28. Minnen, D., Isbell, C., Essa, I., and Starner, T. (2007, January 28–31). Detecting subdimensional motifs: An efficient algorithm for generalized multivariate pattern discovery. Proceedings of the Seventh IEEE International Conference on Data Mining (ICDM 2007), Omaha, NE, USA.10.1109/ICDM.2007.52 ↗
29. Minnen, D., Starner, T., Essa, I.A., and Isbell, C.L. (2007, January 6–12). Improving Activity Discovery with Automatic Neighborhood Estimation. Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India.
30. Discovering multivariate motifs using subsequence density estimation and greedy mixture learning
31. Minnen, D., Starner, T., Essa, I., and Isbell, C. (2006, January 11–14). Discovering characteristic actions from on-body sensor data. Proceedings of the 10th IEEE International Symposium on Wearable Computers, Montreux, Switzerland.10.1109/ISWC.2006.286337 ↗
32. Lowe, D.G. (1999, January 20–25). Object Recognition from Local Scale-Invariant Features. Proceedings of the International Conference on Computer Vision, ICCV ’99, Corfu, Greece.10.1109/ICCV.1999.790410 ↗
33. Distinctive Image Features from Scale-Invariant Keypoints10.1023/B:VISI.0000029664.99615.94 ↗
34. Garg, Y., and Poccia, S.R. (2017, January 6–9). On the Effectiveness of Distance Measures for Similarity Search in Multi-Variate Sensory Data: Effectiveness of Distance Measures for Similarity Search. Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval, ICMR 2017, Bucharest, Romania.10.1145/3078971.3079009 ↗
35. Ester, M., Kriegel, H.P., Sander, J., and Xu, X. (1996, January 2–4). A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD’96, Portland, OR, USA.
36. (2021, May 20). Energy Data for a Building with 27 Zones. Available online: https://drive.google.com/file/d/1qeL6u5Ik5hMSYDeVFp4WpweHQxQ_JZRH/view?usp=sharing.
37. (2021, May 20). BirdSong (13 MFCC Coefficients for 154 Bird Calls). Available online: http://www.xeno-canto.org/explore/taxonomy.