Over the past two decades, time series motif discovery has become a crucial subroutine for many time series data mining tasks; concurrently, it has been established that Dynamic Time Warping (DTW) outperforms other similarity measures like Euclidean Distance in most scenarios. Against this backdrop, a DTW motif discovery algorithm was recently developed; however, it is confined to working with fixed-length subsequences. In this work, we propose a novel approach that allows us to find motifs under both length differences and warping. Our algorithm exploits a promising time series representation called Spikelets and introduces the first lower bound for DTW in the Spikelet space. Extensive empirical studies demonstrate that our method scales effectively across various real-world datasets and efficiently identifies DTW motif pairs of different lengths.

Over the last two decades, time series motif discovery has emerged as a useful primitive; in parallel, it has been known that Dynamic Time Warping (DTW) outperforms other similarity measures, such as Euclidean Distance, under most settings. In this background, an algorithm for scalable DTW motif discovery was proposed; however, it is limited to one-dimensional (1D) and fixed-length subsequences. In contrast, two-dimensional (2D) DTW presents distinct challenges as it involves warping against the target time series and managing lags between dimensions. We propose a general symbolic representation for 2D time series, enabling the discovery of arbitrary-length motifs with warping and lags. In the motion capture (MoCap) community, a ’text-like representation’ for similarity search has been previously proposed. However, it requires multiple parameters and an exhaustive dataset. In contrast, our method relies on just one parameter: the “magnitude threshold,” which captures the value fluctuations without requiring an exhaustive dataset. Furthermore, we empirically demonstrate that our method is scalable enough for various real-world datasets and can effectively identify 2D DTW motifs of arbitrary lengths.

In recent years there has been increasing evidence that one of the simplest time series anomaly detection methods, time series discords, remains one of the most effective methods. However, time series discords have one notable issue; the anomalies discovered depend on the algorithm’s only input parameter, the subsequence length. The obvious way to bypass this issue is to find anomalies at every possible length, however this seems to be untenably slow. In this work we introduce MADRID, an algorithm to efficiently solve the all-discords problem. We show that we can reduce the absolute time to compute all-discords, and that by using a novel computation ordering strategy, MADRID is a Hyper-Anytime Algorithm. We will formally define this term later, but this refers to an anytime algorithm that converges exceptionally fast. In practice this means that for most real-world analytical tasks, the user can interact with their data in real-time. The ability to compute anomalies of all lengths produces the issue of ranking anomalies of different lengths. We further introduce novel algorithms for this task. We demonstrate the utility of MADRID in various domains and show that it allows us to Find anomalies that would otherwise escape our attention.

Over the last two decades, time series motif discovery has emerged as a useful primitive for many downstream analytical tasks, including clustering, classification, rule discovery, segmentation, and summarization. In parallel, it has long been known that Dynamic Time Warping (DTW) is superior to other similarity measures such as Euclidean Distance under most settings. Recently an algorithm to allow scalable DTW motif discovery was proposed; however, it is limited to finding pairs of subsequences whose subsequence lengths are the same. Moreover, that length must be provided by the user ahead of time. In this work, we propose a novel method to discover "warped" motifs whose lengths may differ. Moreover, our method allows input parameters that are not fixed lengths but rather just bounds on the maximum length of motifs to find. This allows us to quickly find different-length motifs without the burdensome trial-and-error of conventional methods. With extensive empirical work, we show that our method is scalable enough for real-world datasets and enables us to find variable-length and "warped" motifs that would otherwise escape the attention of conventional algorithms.

Time series motifs have become a fundamental tool to characterize repeated and conserved structures in systems, such as manufacturing, human behavior and economic activities. Recently the notion of semantic motif was introduced as a generalization of motifs that allows the capture of higher-level semantic structure. Sematic motifs are a very promising primitive; however, the original work characterizes a semantic motif with only two sub-patterns separated by a variable length don’t-care region, so it may fail to capture certain types of regularities embedded in a time series. To mitigate this weakness, we propose an adaptive, symbolic and spike-based approximation that allows overlapping segmentation, which we call spikelet. The adaptive and overlapping nature of our representation is more expressive, enabling it to capture both global and local characteristics of a conserved structure. Furthermore, the symbolic nature of our proposed representation enables us to reason about the “grammatical” structure of the data. With extensive empirical work, we show that spikelet-based algorithms are scalable enough for real-world datasets and enables us to find the higher-level structure that would otherwise escape our attention.

Time series anomaly detection remains a perennially important research topic. If anything, it is a task that has become increasingly important in the burgeoning age of IoT. While there are hundreds of anomaly detection methods in the literature, one definition, time series discords, has emerged as a competitive and popular choice for practitioners. Time series discords are subsequences of a time series that are maximally far away from their nearest neighbors. Perhaps the most attractive feature of discords is their simplicity. Unlike many parameter laden methods, discords require only a single parameter to be set by the user: the subsequence length. In this work we argue that the utility of discords is reduced by sensitivity to this single user choice. The obvious solution to this problem, computing discords of all lengths then selecting the best anomalies (under some measure), seems to be computationally untenable. However, in this work we introduce MERLIN, an algorithm that can efficiently and exactly find discords of all lengths in massive time series archives.

Time series motifs have become a fundamental tool to characterize repeated and conserved structure in systems, such as manufacturing telemetry, economic activities, and both human physiological and cultural behaviors. Recently time series chains were introduced as a generalization of time series motifs to represent evolving patterns in time series, in order to characterize the evolution of systems. Time series chains are a very promising primitive; however, we have observed that the original definition can be brittle in the sense that a small fluctuation in time series may "cut" a chain. Furthermore, the original definition does not provide a measure of the "significance" of a chain, and therefore cannot support top-k search for chains or provide a mechanism to discard spurious chains that might be discovered when searching large datasets. Inspired by observations from dynamical systems theory, this paper introduces two novel quality metrics for time series chains, directionality and graduality, to improve robustness and to enable top-K search. With extensive empirical work we show that our proposed definition is much more robust to the vagaries of real-word datasets and allows us to find unexpected regularities in time series datasets.