Dynamic Time Warping (Dynamic Time Warping)

From Algorithm Wiki
Jump to navigation Jump to search


Fix a metric space $(M, d)$. A sequence of points in $M$ is called a curve. Consider two curves $x, y$ of length $n, m (n \geq m)$. We may traverse $x$ and $y$ by starting in their first entries, in any time step advancing to the next entry in $x$ or $y$ or both, and ending in their last entries. The cost of such a traversal is the sum over all points in time of the distance between the current entries. The dynamic time warping distance of $x$ and $y$ is the minimal cost of any traversal.


$n$: length of first curve

$m$: length of second curve

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem Implication Year Citation Reduction
UOV If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$
Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$
2015 https://arxiv.org/pdf/1502.01063.pdf link