Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching

Abstract

In a way similar to the string-to-string correction problem we address time series similarity in the 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, Longest Common Subsequence or Edit Distance with Real Penalty algorithms. In particular, it highlights a parameter which drives a kind of stiffness of the elastic measure along the time axis. We show that the similarity provided by TWED is a metric potentially useful 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 relate the matching of time series into down sampled representation spaces to the matching into the original space. Empiric quality of the TWED distance is evaluated on a simple classification task. Compared to Edit Distance, Dynamic Time Warping, Longest Common Subsequnce and Edit Distance with Real Penalty, TWED has proven to be quite effective on the considered experimental task.

References in corpus (2)

• Speeding up Simplification of Polygonal Curves using Nested Approximations
• Time Warp Edit Distance

Cited by in corpus (34)

• InceptionTime: Finding AlexNet for Time Series Classification
• An Empirical Evaluation of Similarity Measures for Time Series Classification
• TS-CHIEF: A Scalable and Accurate Forest Algorithm for Time Series Classification
• Bake off redux: a review and experimental evaluation of recent time series classification algorithms
• Proximity Forest: An effective and scalable distance-based classifier for time series
• A Review and Evaluation of Elastic Distance Functions for Time Series Clustering
• On Recursive Edit Distance Kernels with Application to Time Series Classification
• Expert enhanced dynamic time warping based anomaly detection
• Unsupervised Classification of Variable Stars
• The Extended Edit Distance Metric
• Sparsification of the Alignment Path Search Space in Dynamic Time Warping
• Speeding up Simplification of Polygonal Curves using Nested Approximations
• Comparing Clustering Approaches for Smart Meter Time Series: Investigating the Influence of Dataset Properties on Performance
• NeuralWarp: Time-Series Similarity with Warping Networks
• Times series averaging from a probabilistic interpretation of time-elastic kernel
• Times series averaging and denoising from a probabilistic perspective on time-elastic kernels
• Autowarp: Learning a Warping Distance from Unlabeled Time Series Using Sequence Autoencoders
• A tale of two toolkits, report the first: benchmarking time series classification algorithms for correctness and efficiency
• Time Warp Edit Distance
• Discrete Elastic Inner Vector Spaces with Application in Time Series and Sequence Mining
• Affine and Regional Dynamic Time Warpng
• Predictive Modelling of Bone Age through Classification and Regression of Bone Shapes
• Use Short Isometric Shapelets to Accelerate Binary Time Series Classification
• Attention to Warp: Deep Metric Learning for Multivariate Time Series
• Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering
• Semi-Metrification of the Dynamic Time Warping Distance
• Early Abandoning PrunedDTW and its application to similarity search
• Learnable Dynamic Temporal Pooling for Time Series Classification
• Improved Time Warp Edit Distance -- A Parallel Dynamic Program in Linear Memory
• Report: Dynamic Eye Movement Matching and Visualization Tool in Neuro Gesture
• Adaptive Down-Sampling and Dimension Reduction in Time Elastic Kernel Machines for Efficient Recognition of Isolated Gestures
• The Influence of Global Constraints on Similarity Measures for Time-Series Databases
• Assessing pattern recognition or labeling in streams of temporal data
• More sophisticated is not always better: comparison of similarity measures for unsupervised learning of pathways in biomolecular simulations