MotiPlus and MotiSet: Discovering the Best Set of Motiflets in Time Series

Abstract

Motif discovery algorithms find repeating patterns in time series with high similarity. Many methods exist for this important task, which has numerous applications. This work is guided by the following two ambitious questions: What is the “perfect” motif? What is the “perfect” set of motifs? To answer the first question, we consider all motifs of a certain size and rank them based on a robust measure of similarity. To determine the optimal size of a motif, we assess the quality of a motif relative to a lattice of sub- and supermotifs and define two novel quality constraints. To answer the second question, we balance multiple contrastive quality criteria for a set of motifs. The set of motifs should be diverse, non-redundant, and include highly similar motifs of varying sizes. Due to the exponential search space, the exact search for the best motif and set of motifs is a major concern. We leverage the lattice structure of time series and prune most candidate motifs and sets of motifs. For discovering a set of motifs, we propose two variations. The first is based on a greedy search and filters using the aforementioned quality constraints. The second algorithm is based on A* search, by directly measuring the quality of thousands of candidate sets of motifs. We evaluate our method qualitatively on music datasets and quantitatively on a time series motif discovery benchmark. The proposed algorithms achieve state-of-the-art results, improving precision by 27.9% and recall by 10.1% over LoCoMotif , and significantly outperforming strong baselines like Grammarviz , MMotif , and Motiflets .