Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching
By Pierre-Francois Marteau. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007
363 citations recorded by the source corpus.
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). TWED is slightly different in form from dynamic time warping (DTW), longest common subsequence (LCSS), or edit distance with real penalty (ERP) algorithms. In particular, it highlights a parameter that controls a kind of stiffness of the elastic measure along the time axis. We show that the similarity provided by TWED is a potentially useful metric in time series retrieval applications since it could benefit from the triangular inequality property to speed up the retrieval process while tuning the parameters of the elastic measure. In that context, a lower bound is derived to link the matching of time series into down sampled representation spaces to the matching into the original space. The empiric quality of the TWED distance is evaluated on a simple classification task. Compared to edit distance, DTW, LCSS, and ERP, TWED has proved to be quite effective on the considered experimental task.
Subfields: Signal Processing
View Paper: https://www.semanticscholar.org/paper/3817a4924a0d21c7d688a0d621370e86705a5cbb
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Signal Processing
- Anthony J. Bagnall
- Jason Lines
- Aaron Bostrom
- Rohit J. Kate
- James Large
- Jessica Lin
- Eamonn J. Keogh
- Jon Hills
Citations in the corpus
- Time-Series Classification with COTE: The Collective of Transformation-Based Ensembles (2015, background): “The establishment of the UCR repository for TSC problems [1] has engendered growth in the number of algorithms proposed for TSC (for example, see [2], [3], [4], [5], [6], [7], [8], [9]).”
- The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances (2016, methodology): “Marteau proposes the TWE distance (Marteau 2009), an elastic distance metric that includes characteristics from both LCSS and DTW.”
- Rotation-invariant similarity in time series using bag-of-patterns representation (2012, background): “Other elastic distance measures exist for time series, such as Longest Common SubSequence (LCSS) (Vlachos et al. 2002), Edit distance with Real Penalty (ERP) (Chen and Ng 2004) and Time-Warp Edit Distance (TWED) (Marteau 2009).”
- Optimal Matching Analysis and Life-Course Data: The Importance of Duration (2010, neutral): “as Clote and Straubhaar (2006), who propose a time-warping which is not only symmetric between pairs of sequences but also symmetric in time, and Marteau (2007) , who proposes a penalty for the”