Dynamic Time Warping (Dynamic Time Warping)

Description

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.

Parameters

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