# Dynamic Time Warping (Dynamic Time Warping)

Jump to navigation
Jump to search

## 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 |