Faster Sequential Search with a Two-Pass Dynamic-Time-Warping Lower Bound

2008/07/10 by Daniel Lemire, Lemire, Daniel
Computer Science · #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Time Series Analysis and Forecasting #Video Analysis and Summarization #cs.DB

paper · pdf · doi:10.48550/arxiv.0807.1734

openalex publication_date 2008/07/10 · arxiv created 2008/10/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 for sequential search. As an example, our approach is 3 times faster over random-walk and shape time series. We also review some of the mathematical properties of the DTW. We derive a tight triangle inequality for the DTW. We show that the DTW becomes the l₁ distance when time series are separated by a constant.

Citations

• Dynamic programming algorithm optimization for spoken word recognition

Related

• Exact Indexing of Time Series under Dynamic Time Warping
• Elastic bands across the path: A new framework and methods to lower bound DTW
• Early Abandoning PrunedDTW and its application to similarity search
• Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series
• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length