Discovering Subdimensional Motifs of Different Lengths in Large-Scale Multivariate Time Series

--Detecting repeating patterns of different lengths in time series, also called variable-length motifs, has received a great amount of attention by researchers and practitioners. Despite the significant progress that has been made in recent single dimensional variable-length motif discovery work, detecting variable-length subdimensional motifs --patterns that are simultaneously occurring only in a subset of dimensions in multivariate time series--remains a difficult task. The main challenge is scalability. On the one hand, the brute-force enumeration solution, which searches for motifs of all possible lengths, is very time consuming even in single dimensional time series. On the other hand, previous work show that index-based fixed-length approximate motif discovery algorithms such as random projection are not suitable for detecting variable-length motifs due to memory requirement. In this paper, we introduce an approximate variable-length subdimensional motif discovery algorithm called Collaborative HIerarchy based Motif Enumeration (CHIME) to efficiently detect variable-length subdimensional motifs given a minimum motif length in large-scale multivariate time series. We show that the memory cost of the approach is significantly smaller than that of random projection. Moreover, the speed of the proposed algorithm is significantly faster than that of the state-of-the-art algorithms. We demonstrate that CHIME can efficiently detect meaningful variable-length subdimensional motifs in large real world multivariate time series datasets. I NTRODUCTION Detecting repeating patterns of various lengths, also called variable-length motifs, in time series has received a great amount of attention [1] [2] [3] [4]. Since motifs of different lengths can naturally coexist in a time series, detecting variable-length motifs often is a necessary step for many real-world applications such as classification [2], anomaly detection [5] and data visualization [6]. Contrary to the significant progress that has been made in recent single dimensional variable-length motif discovery work [2] [3] [7], only little progress is made in detecting variable-length subdimensional motifs [8] [9] -- patterns that are simultaneously occurring only in a subset of all dimensions in multivariate time series. Existing approaches [10] [8] [9] in subdimensional motif discovery still only detect motifs of a specified length, possibly suggested by domain experts. While in some applications, these approaches may fit well if domain knowledge is available and a good motif length can be specified by the user, we aim at solving the problem in a more general case -- when the correct motif length is not known, or motifs of various lengths coexist in the data. One is labeled in red line and occurs in dimension {D 1,D 2} with length 200.