2008/11/30 by Daniel Lemire · 186 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Bounding overwatch #Combinatorics #Computation #Computer science #Data Management and Algorithms #Data mining #Dynamic time warping #Geometry #Image (mathematics) #Image warping #Mathematics #Measure (data warehouse) #Music and Audio Processing #Pattern recognition (psychology) #Quadratic equation #Random walk #Series (stratigraphy) #Similarity (geometry) #Similarity measure #Statistics #Time Series Analysis and Forecasting #Time complexity #Triangle inequality #Upper and lower bounds #cs.CV #cs.DB
paper · pdf · doi:10.1016/j.patcog.2008.11.030
published in Pattern Recognition 42(9), 2169-2180 (Elsevier BV) · Accepted in Pattern Recognition on November 20th, 2008
openalex publication_date 2008/12/11 · arxiv created 2009/06/10 · arxiv updated 2012/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.