Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW

• URL: http://arxiv.org/abs/2009.07907v1
• Date: Wed, 16 Sep 2020 19:35:43 GMT
• Title: Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW
• Authors: Sara Alaee, Kaveh Kamgar, Eamonn Keogh
• Abstract summary: We present the first scalable exact method to discover time series motifs under Dynamic Time Warping. Our algorithm can admissibly prune up to 99.99% of the DTW computations.
• Score: 1.282368486390644
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Over the last decade, 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, there has been an increased understanding that Dynamic Time Warping (DTW) is the best time series similarity measure in a host of settings. Surprisingly however, there has been virtually no work on using DTW to discover motifs. The most obvious explanation of this is the fact that both motif discovery and the use of DTW can be computationally challenging, and the current best mechanisms to address their lethargy are mutually incompatible. In this work, we present the first scalable exact method to discover time series motifs under DTW. Our method automatically performs the best trade-off between time-to-compute and tightness-of-lower-bounds for a novel hierarchy of lower bounds representation we introduce. We show that under realistic settings, our algorithm can admissibly prune up to 99.99% of the DTW computations.

Related papers

• A Dense Reward View on Aligning Text-to-Image Diffusion with Preference [54.43177605637759]
  We propose a tractable alignment objective that emphasizes the initial steps of the T2I reverse chain. In experiments on single and multiple prompt generation, our method is competitive with strong relevant baselines.
  arXiv  Detail & Related papers  (2024-02-13T07:37:24Z)
• OTW: Optimal Transport Warping for Time Series [75.69837166816501]
  Dynamic Time Warping (DTW) has become the pragmatic choice for measuring distance between time series. It suffers from unavoidable quadratic time complexity when the optimal alignment matrix needs to be computed exactly. We introduce a new metric for time series data based on the Optimal Transport framework, called Optimal Transport Warping (OTW)
  arXiv  Detail & Related papers  (2023-06-01T12:45:00Z)
• Deep Declarative Dynamic Time Warping for End-to-End Learning of Alignment Paths [54.53208538517505]
  This paper addresses learning end-to-end models for time series data that include a temporal alignment step via dynamic time warping (DTW) We propose a DTW layer based around bi-level optimisation and deep declarative networks, which we name DecDTW. We show that this property is particularly useful for applications where downstream loss functions are defined on the optimal alignment path itself.
  arXiv  Detail & Related papers  (2023-03-19T21:58:37Z)
• Approximating DTW with a convolutional neural network on EEG data [9.409281517596396]
  We propose a fast and differentiable approximation of Dynamic Time Wrapping (DTW) We show that our methods achieve at least the same level of accuracy as other DTW main approximations with higher computational efficiency.
  arXiv  Detail & Related papers  (2023-01-30T13:27:47Z)
• HyRSM++: Hybrid Relation Guided Temporal Set Matching for Few-shot Action Recognition [51.2715005161475]
  We propose a novel Hybrid Relation guided temporal Set Matching approach for few-shot action recognition. The core idea of HyRSM++ is to integrate all videos within the task to learn discriminative representations. We show that our method achieves state-of-the-art performance under various few-shot settings.
  arXiv  Detail & Related papers  (2023-01-09T13:32:50Z)
• Gait Recognition in the Wild with Multi-hop Temporal Switch [81.35245014397759]
  gait recognition in the wild is a more practical problem that has attracted the attention of the community of multimedia and computer vision. This paper presents a novel multi-hop temporal switch method to achieve effective temporal modeling of gait patterns in real-world scenes.
  arXiv  Detail & Related papers  (2022-09-01T10:46:09Z)
• Dynamic Time Warping based Adversarial Framework for Time-Series Domain [32.45387153404849]
  We propose a novel framework for the time-series domain referred as Dynamic Time Warping for Adrial Robustness (DTW-AR) We develop a principled algorithm justified by theoretical analysis to efficiently create diverse adversarial examples using random alignment paths. Experiments on diverse real-world benchmarks show the effectiveness of DTW-AR to fool DNNs for time-series data and to improve their robustness using adversarial training.
  arXiv  Detail & Related papers  (2022-07-09T17:23:00Z)
• Aligning Time Series on Incomparable Spaces [83.8261699057419]
  We propose Gromov dynamic time warping (GDTW), a distance between time series on potentially incomparable spaces. We demonstrate its effectiveness at aligning, combining and comparing time series living on incomparable spaces.
  arXiv  Detail & Related papers  (2020-06-22T22:19:28Z)
• Exploring time-series motifs through DTW-SOM [3.42658286826597]
  We argue that visually exploring time-series motifs computed by motif discovery algorithms can be useful to understand and debug results. To explore the output of motif discovery algorithms, we propose the use of an adapted Self-Organizing Map, the DTW-SOM. We test DTW-SOM in a synthetic motif dataset and two real time-series datasets from the UCR Time Series Classification Archive.
  arXiv  Detail & Related papers  (2020-04-17T11:21:16Z)
• FastDTW is approximate and Generally Slower than the Algorithm it Approximates [11.689905300531917]
  The Dynamic Time Warping (DTW) distance measure is the best measure to use for most tasks, in most domains. One of the most cited approximate approaches is FastDTW. In any realistic data mining application, the approximate FastDTW is much slower than the exact DTW.
  arXiv  Detail & Related papers  (2020-03-25T07:26:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.