Toward accurate dynamic time warping in linear time and space

By Stan Salvador, Philip Ka-Fai Chan. 2007

1,672 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

TSViz: Demystification of Deep Learning Models for Time-Series Analysis (2018, background): “DTW[i, j] = D(aim,a j n) + min( DTW[i− 1, j]DTW[i, j − 1] DTW[i− 1, j − 1] ) (20) D(aim,a j n) = ‖aim − ajn‖2 (21) Once the DTW matrix is computed, DTW[d, d] can be used as a measure of the minimum possible distance to align the two activation vectors where d is the dimensionality of the activation”
Mobile sensor data anonymization (2018, methodology): “ransformation. The k-Nearest Neighbors. To evaluate the efficiency of the anonymization with another unsupervised mechanism, we implement thek-Nearest Neighbors (k-NN) with Dynamic Time Warping (DTW) [27], which is one of the best methods for clustering time series data17. Using DTW, we measure the ”
Similarity measures for identifying material parameters from hysteresis loops using inverse analysis (2018, background): “In a case where a very large number of points are considered, it may be worthwhile to consider the FastDTW algorithm by Salvador and Chan [38].”
Time-series clustering - A decade review (2015, background): “1) Investigating the mentioned approaches as similarity/ dissimilarity measure, it is implied that the most effective and accurate approaches are the ones which are based on dynamic programming (DP) which are very expensive in time execution (the cost of comparing two time-series is quadratic in the”
Privacy and Utility Preserving Sensor-Data Transformations (2019, methodology): “Finally, to evaluate the privacy loss and eﬃciency of the anonymization with an unsupervised mechanism, we implement the k -Nearest Neighbors ( k -NN) with Dynamic Time Warping (DTW) [47].”
Synthesis of Realistic ECG using Generative Adversarial Networks (2019, methodology): “Due to the large volume of data studied in this work, FastDTW is used to approximate the DTW metric as it reduces the computational time required to calculate DTW to O(N) where N is the number of points in the series [43].”
We Can Hear You with Wi-Fi! (2014, neutral): “For more information, we recommend [40] which describes it in detail.”
Avoiding the crowds: understanding Tube station congestion patterns from trip data (2012, methodology): “In our analysis, we used an approximation to Dynamic Time Warping called FastDTW, that has linear time and space complexity, proved both theoretically and empirically [17].”
Effective and General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping (2019, methodology): “We refer to Salvador and Chan [28] for a proof and pseudo-code.”
Multilingual Byte2Speech Text-To-Speech Models Are Few-shot Spoken Language Learners (2021, methodology): “Also we demonstrate the quality by mean square error (MSE) with ground truth mels both after collapsing unvoiced and dynamic time warping using FastDTW (Salvador & Chan, 2007).”
Gestures without libraries, toolkits or training: a $1 recognizer for user interface prototypes (2007, methodology): “As noted, there are procedures to accelerate DTW [24], but these make it a more complicated algorithm, which runs counter to our motivation for this work.”
Towards Robust Skill Generalization: Unifying Learning from Demonstration and Motion Planning (2017, methodology): “The end-effector positions over time were recorded and the trajectories were temporally aligned using dynamic time warping [31].”
Dude, where's my card?: RFID positioning that works with multipath and non-line of sight (2013, methodology): “8, PinIt uses a standard solver for DTW based on dynamic programming with linear complexity [37].”
Learning-Based Methods for Comparing Sequences, with Applications to Audio-to-MIDI Alignment and Matching (2016, methodology): “A better approach may be to simultaneously learn more and more efficient representations by repeatedly downsampling to coarser timescales, as is done in FastDTW (Salvador and Chan, 2007).”