Finding Repeated Structures in Time Series: Algorithms and Applications: A Unifying View of Time Series Motifs/Shapelets/Chains and Similar Primitives

Repeated structures in time series (time series motifs) are interesting in their own right and are often used in downstream algorithms for tasks as diverse as classification, clustering, rule-discovery, segmentation, summarization, compression and anomaly detection.If a structure is repeated, that hints at some mechanism of conservation, and the discovery of conserved structure is one of the most basic tools/goals of science.In this survey (which is a companion to a tutorial) I show the two key ideas needed to do successful time series motif discovery.First, making a computationally hard problem tractable; by the use of anytime algorithms, contract algorithms and specialist hardware.I will further review work on how to obtain more meaningful results by considering additional constraints on the returned patterns.For example, class conditional motifs (i.e.shapelets), motifs with a drift (i.e.time series chains), motifs that exist in two or more time series (motif-joins, consensus motifs), range motifs, KNN motifs etc.The companion tutorial is illustrated with novel interesting examples from science, industry, entertainment and medicine.Moreover, the tutorial slides will contain code snippets and a data archive that will allow the community to reproduce all the results and then generalize them to their own domain of interest.