Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound

Abstract

The Dynamic Time Warping (DTW) is a popular similarity measure between time series. The DTW fails to satisfy the triangle inequality and its computation requires quadratic time. Hence, to find closest neighbors quickly, we use bounding techniques. We can avoid most DTW computations with an inexpensive lower bound (LB Keogh). We compare LB Keogh with a tighter lower bound (LB Improved). We find that LB Improved-based search is faster. As an example, our approach is 2-3 times faster over random-walk and shape time series.

Accepted in Pattern Recognition on November 20th, 2008

References in corpus (1)

• Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element

Cited by in corpus (17)

• Geometric Feature-Based Facial Expression Recognition in Image Sequences Using Multi-Class AdaBoost and Support Vector Machines
• An Empirical Evaluation of Similarity Measures for Time Series Classification
• Proximity Forest: An effective and scalable distance-based classifier for time series
• SparseDTW: A Novel Approach to Speed up Dynamic Time Warping
• Dynamic Time Warping as a New Evaluation for Dst Forecast with Machine Learning
• Time Series Classification by Class-Specific Mahalanobis Distance Measures
• Scoring and Assessment in Medical VR Training Simulators with Dynamic Time Series Classification
• Tight lower bounds for Dynamic Time Warping
• Experimental Comparison of Representation Methods and Distance Measures for Time Series Data
• Leveraging the Channel as a Sensor: Real-time Vehicle Classification Using Multidimensional Radio-fingerprinting
• Data-Driven Modeling of Noise Time Series with Convolutional Generative Adversarial Networks
• Scalable Comparison of JavaScript V8 Bytecode Traces
• TC-DTW: Accelerating Multivariate Dynamic Time Warping Through Triangle Inequality and Point Clustering
• Semi-Metrification of the Dynamic Time Warping Distance
• An Analytical Approach to Improving Time Warping on Multidimensional Time Series
• Aligning Time Series on Incomparable Spaces
• Orientation-Preserving Vectorized Distance Between Curves