Binary Dynamic Time Warping in Linear Time

Dynamic time warping distance (DTW) is a widely used distance measure between time series $x,y\in {\mathrm{\Sigma }}^n$. It was shown by Abboud, Backurs, and Williams that in the \emph{binary case}, where $\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }=2$, DTW can be computed in time $O(n^{1.87})$. We improve this running time $O(n)$. Moreover, if $x$ and $y$ are run-length encoded, then there is an algorithm running in time $\tilde{O}(k+\mathrm{\ell })$, where $k$ and $\mathrm{\ell }$ are the number of runs in $x$ and $y$, respectively. This improves on the previous best bound of $O(k\mathrm{\ell })$ due to Dupont and Marteau.