Dynamic Time Warping: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE: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 curr...") |
No edit summary |
||
| Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n: length of first curve | |||
m: length of second curve | |||
m: length of second curve | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 13:04, 15 February 2023
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 |