Elastic Bands Across The Path: A New Framework And Methods To Lower Bound DTW

Abstract

There has been renewed recent interest in developing effective lower bounds for Dynamic Time Warping (DTW) distance between time series. These have many applications in time series indexing, clustering, forecasting, regression and classification. One of the key time series classification algorithms, the nearest neighbor algorithm with DTW distance (NN-DTW) is very expensive to compute, due to the quadratic complexity of DTW. Lower bound search can speed up NN-DTW substantially. An effective and tight lower bound quickly prunes off unpromising nearest neighbor candidates from the search space and minimises the number of the costly DTW computations. The speed up provided by lower bound search becomes increasingly critical as training set size increases. Different lower bounds provide different trade-offs between computation time and tightness. Most existing lower bounds interact with DTW warping window sizes. They are very tight and effective at smaller warping window sizes, but become l

Stats

• citations23
• S2 citations—
• github stars0
• HF likes0
• heat score10.35
• arxiv keytan2018elastic

Related papers

• Asymmetric Learning Vector Quantization For Efficient Nearest Neighbor Classification In Dynamic Time Warping Spaces (2017)9.92
• Drop-dtw: Aligning Common Signal Between Sequences While Dropping Outliers (2021)0.00
• Optimal Hashing-based Time-space Trade-offs For Approximate Near Neighbors (2016)11.29
• Sublinear Time Nearest Neighbor Search Over Generalized Weighted Manhattan Distance (2021)0.00
• Pruning Algorithms For Low-dimensional Non-metric K-nn Search: A Case Study (2019)2.26
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories (2020)6.34
• Worst-case Performance Of Popular Approximate Nearest Neighbor Search Implementations: Guarantees And Limitations (2023)5.84
• Scalable Nearest Neighbor Search For Optimal Transport (2019)0.00