Dynamic Time Warping in the Low-Distance Regime

Itai Boneh, Shay Golan, Tomasz Kociumaka

Dynamic Time Warping (DTW) is a classical similarity measure for strings and time series that allows local stretching. Given non-empty strings $S,T$ over an alphabet $\Sigma$ and a cost…