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

2008-11-20 · Daniel Lemire

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.

📄 PDF Abstract BibTeX arXiv:0811.3301

Code (1)

lemire/lbimproved 공식 구현

Tasks

Dynamic Time WarpingRetrievalTime SeriesTime Series Analysis Vocal Bursts Valence Prediction

Methods 이 논문이 사용한 방법론

DTW Dynamic Time Warping (DTW) [1] is one of well-known distance measures between a pairwise of time series. The main idea of DTW is to compute the distance from the matching of…

Fast dynamic time warping and clustering in C++

2023-07-10 · Volkan Kumtepeli, Rebecca Perriment, David A. Howey

We present an approach for computationally efficient dynamic time warping (DTW) and clustering of time-series data. The method frames the dynamic warping of time series datasets as an optimisation problem solved using dy…

Clustering Dynamic Time Warping Time Series

DTW-Align: Bridging the Modality Gap in End-to-End Speech Translation with Dynamic Time Warping Alignment

2025-09-23 · Abderrahmane Issam, Yusuf Can Semerci, Jan Scholtes, Gerasimos Spanakis arxiv

End-to-End Speech Translation (E2E-ST) is the task of translating source speech directly into target text bypassing the intermediate transcription step. The representation discrepancy between the speech and text modaliti…

Variable Sampling MPC via Differentiable Time-Warping Function

2023-01-20 · Zehui Lu, Shaoshuai Mou

Designing control inputs for a system that involves dynamical responses in multiple timescales is nontrivial. This paper proposes a parameterized time-warping function to enable a non-uniformly sampling along a predictio…

Time-Warping Recurrent Neural Networks for Transfer Learning

2026-04-02 · Jonathon Hirschi arxiv

Dynamical systems describe how a physical system evolves over time. Physical processes can evolve faster or slower in different environmental conditions. We use time-warping as rescaling the time in a model of a physical…

Transfer Learning

Dynamic Boundary Time Warping for Sub-sequence Matching with Few Examples

2020-10-27 · Łukasz Borchmann, Dawid Jurkiewicz, Filip Graliński, Tomasz Górecki

The paper presents a novel method of finding a fragment in a long temporal sequence similar to the set of shorter sequences. We are the first to propose an algorithm for such a search that does not rely on computing the …

Dynamic Time Warping Retrieval Semantic Retrieval