Discovering Leitmotifs in Multidimensional Time Series

Download PDF

Abstract

A leitmotif is a recurring theme in literature, movies or music that carries symbolic significance for the piece it is contained in. When this piece can be represented as a multi-dimensional time series (MDTS), such as acoustic or visual observations, finding a leitmotif is equivalent to the pattern discovery problem, which is an unsu-is equivalent to the pattern discovery problem, which is an unsupervised and complex problem in time series analytics. Compared to the univariate case, it carries additional complexity because pat-to the univariate case, it carries additional complexity because patterns typically do not occur in all dimensions but only in a few -terns typically do not occur in all dimensions but only in a few which are, however, unknown and must be detected by the method itself. In this paper, we present the novel, efficient and highly effect-itself. In this paper, we present the novel, efficient and highly effective leitmotif discovery algorithm LAMA for MDTS. LAMA rests on two core principals: (a) a leitmotif manifests solely given a yet unknown number of sub-dimensions - neither too few, nor too many, and (b) the set of sub-dimensions are not independent from the best pattern found therein, necessitating both problems to be approached in a joint manner. In contrast to most previous methods, LAMA tackles both problems jointly - instead of independently se-LAMA tackles both problems jointly - instead of independently selecting dimensions (or leitmotifs) and finding the best leitmotifs (or dimensions). Our experimental evaluation on a novel ground-truth annotated benchmark of 14 distinct real-life data sets shows that LAMA, when compared to four state-of-the-art baselines, shows superior performance in detecting meaningful patterns without increased computational complexity. KEYWORDS Multidimensional, Sub-Dimensional, Multivariate, Time Series, Mo-Multidimensional, Sub-Dimensional, Multivariate, Time Series, Motif, Motif Set, Leitmotif