# Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching

@article{Marteau2009TimeWE, title={Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching}, author={Pierre-François Marteau}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, year={2009}, volume={31}, pages={306-318} }

In a way similar to the string-to-string correction problem, we address discrete time series similarity in light of a time-series-to-time-series-correction problem for which the similarity between two time series is measured as the minimum cost sequence of edit operations needed to transform one time series into another. To define the edit operations, we use the paradigm of a graphical editing process and end up with a dynamic programming algorithm that we call time warp edit distance (TWED… Expand

#### 231 Citations

Pf Marteau, September 2006 "time Warp Edit Distances with Stiffness Adjustment for Time Series Matching" 1

- 2008

In a way similar to the string-to-string correction problem we address time series similarity in light of a time-series-to-time-series-correction problem for which the similarity between two time… Expand

Improved Time Warp Edit Distance - A Parallel Dynamic Program in Linear Memory

- Computer Science, Mathematics
- ArXiv
- 2020

A novel Improved Time Warp Edit Distance algorithm that is both massively parallelizable and requiring only linear storage is presented, which uses the procession of a three diagonal band to cover the original dynamic program space. Expand

Time Alignment Measurement for Time Series

- Computer Science
- Pattern Recognit.
- 2018

A novel measurement called Time Alignment Measurement is proposed, which delivers similarity information on the temporal domain and demonstrates the potential of the approach in measuring performance of time series alignment methodologies and in the characterization of synthetic and real time series data acquired during human movement. Expand

Sparsification of the Alignment Path Search Space in Dynamic Time Warping

- Computer Science, Mathematics
- Appl. Soft Comput.
- 2019

The sparsification of the alignment path search space for DTW-like measures is addressed, essentially to lower their computational cost without loosing on the quality of the measure, and two new (dis)similarity measures are proposed for time series comparison. Expand

Interactive Time Series Exploration Powered by the Marriage of Similarity Distances

- Computer Science
- Proc. VLDB Endow.
- 2016

This work proposes a novel paradigm called Online Exploration of Time Series (ONEX) employing a powerful one-time preprocessing step that encodes critical similarity relationships to support subsequent rapid data exploration and offers a truly interactive exploration experience supporting novel time series operations. Expand

Speeding up similarity search under dynamic time warping by pruning unpromising alignments

- Computer Science
- Data Mining and Knowledge Discovery
- 2018

The longer the time needed for the search, the higher the speedup ratio achieved by the method, and it is demonstrated that the method performs similarly to UCR suite for small queries and narrow warping constraints, but performs up to five times faster for long queries and large warping windows. Expand

Novel Approaches Towards Fast and Accurate Time series Classification

- Computer Science
- 2018

A new DTW approximation method is proposed which works for all type of time series (even without repetition of values), and the effectiveness of the 3D DTW and BDTW are shown on different applications. Expand

Time Warp Edit Distance

- Computer Science
- ArXiv
- 2008

This family of time warp distances is constructed as an editing distance whose elementary operations apply on linear segments that is well suited for the processing of event data for which each data sample is associated with a timestamp, not necessarily obtained according to a constant sampling rate. Expand

Time series classification with ensembles of elastic distance measures

- Mathematics, Computer Science
- Data Mining and Knowledge Discovery
- 2014

This work believes that their ensemble is the first ever classifier to significantly outperform DTW and raises the bar for future work in this area, and demonstrates that the ensemble is more accurate than approaches not based in the time domain. Expand

Affine and Regional Dynamic Time Warping

- Mathematics, Computer Science
- 2015 IEEE International Conference on Data Mining Workshop (ICDMW)
- 2015

The proposed alignment methods outperform DTW on specific simulated datasets, and one-nearest-neighbor classifiers using their associated difference measures are competitive with the difference measures associated with state-of-the-art alignment methods on real datasets. Expand

#### References

SHOWING 1-10 OF 65 REFERENCES

Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching

- Computer Science
- 2009

This work addresses discrete time series similarity in light of a time-series-to-time- series-correction problem for which the similarity between time series and series is close to zero. Expand

Using Edit Distance in Point-Pattern Matching

- Computer Science
- SPIRE
- 2001

The main motivation for these methods is two and higher dimensional point-pattern matching, and therefore they generalize these methods into the 2D case, and it is shown that this generalization leads to an NP-complete problem. Expand

Time Warp Edit Distance

- Computer Science
- ArXiv
- 2008

This family of time warp distances is constructed as an editing distance whose elementary operations apply on linear segments that is well suited for the processing of event data for which each data sample is associated with a timestamp, not necessarily obtained according to a constant sampling rate. Expand

Indexing multi-dimensional time-series with support for multiple distance measures

- Computer Science, Mathematics
- KDD '03
- 2003

The experimental results demonstrate that the index motivated by the need for a single index structure that can support multiple distance measures can help speed-up the computation of expensive similarity measures such as the LCSS and the DTW. Expand

Robust and fast similarity search for moving object trajectories

- Computer Science
- SIGMOD '05
- 2005

Analysis and comparison of EDR with other popular distance functions, such as Euclidean distance, Dynamic Time Warping (DTW), Edit distance with Real Penalty (ERP), and Longest Common Subsequences, indicate that EDR is more robust than Euclideans distance, DTW and ERP, and it is on average 50% more accurate than LCSS. Expand

Making Time-Series Classification More Accurate Using Learned Constraints

- Computer Science
- SDM
- 2004

This work targets the accuracy aspect of DTW performance and introduces a new framework that learns arbitrary constraints on the warping path of the DTW calculation and speeds up DTW by a wide margin. Expand

On The Marriage of Lp-norms and Edit Distance

- Computer Science
- VLDB
- 2004

A new distance function, which is a marriage of L1- norm and the edit distance, ERP, which can support local time shifting, and is a metric, and dominates all existing strategies. Expand

Fast time series classification using numerosity reduction

- Computer Science
- ICML
- 2006

While the idea of numerosity reduction for nearest-neighbor classifiers has a long history, it is shown here that it can leverage off an original observation about the relationship between dataset size and DTW constraints to produce an extremely compact dataset with little or no loss in accuracy. Expand

Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

- Mathematics, Computer Science
- Knowledge and Information Systems
- 2001

This work introduces a new dimensionality reduction technique which it is called Piecewise Aggregate Approximation (PAA), and theoretically and empirically compare it to the other techniques and demonstrate its superiority. Expand

Adaptive Multiresolution and Dedicated Elastic Matching in Linear Time Complexity for Time Series Data Mining

- Mathematics, Computer Science
- Sixth International Conference on Intelligent Systems Design and Applications
- 2006

An adaptive multiresolution approach to the problem of multidimensional time series characterization is developed and a dedicated elastic pseudo distance is provided to support similarity search mechanisms for such characterization. Expand