# Talk:Dynamic time warping

WikiProject Mathematics (Rated Start-class, Low-priority)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 Start Class
 Low Priority
Field:  Applied mathematics

## Suggested errors and improvments

It would be nice if there was an example or note how can be the DTW array used afterwards. Petulda (talk) 16:28, 19 December 2009 (UTC)

I believe that the second algorithm is wrong. As it is, it reads unitialized memory when j=i-w or j=i+w. A simple solution would be to initialize the whole matrix with infinity. 201.79.213.251 (talk) 14:33, 19 December 2009 (UTC)

The distance d is defined in the text, please don't pass it as a matrix to the function. That's silly. —Preceding unsigned comment added by 96.20.156.153 (talk) 12:52, 20 November 2009 (UTC)

Can someone please explain the difference between DTW and Levenshtein distance?

The displayed algorithm is actually the Levenstein distance. The Levenstein or string edit distance is a particular case of DTW, when the sequences consist of discrete symbol, and the distance between any two different symbols (including the 'empty' symbol) is 1, and 0 for identical symbols. However, in its most general form, the sequences may consist of continuous feature vectors. I think this should be made clear in the page. —Preceding unsigned comment added by 131.231.126.100 (talk) 12:04, 16 December 2008 (UTC)

The algorithms look almost identical. Prehaps a translation of both into C would claify this?

No. All algorithms should be in pseudocode. Obviously.65.183.135.231 (talk) 04:37, 20 April 2008 (UTC)
The obviousness escapes me. You can't compare two pseudocodes. 70.225.163.208 (talk) 01:09, 17 June 2011 (UTC)

This statement seems to be false: "The extension of the problem for two-dimensional "series" like images (planar warping) is NP-complete, while the problem for one-dimensional signals like time series can be solved in polynomial time." All 2-D, n-D series can be serialized (and usually are). The NP-complete assertion is also unreferenced.Enon (talk) 03:46, 26 July 2010 (UTC)

The thing is that if you serialize a 2d sequence (e.g., concatenate the rows of an image), you loose the connections between each pixel and its neighbors above and below, and can match only in the horizontal direction, each row indepent of the other rows. For example, if you want to match the pixels of two images, you get a pretty stripey correspondence map. --IdS (talk) 21:57, 20 March 2011 (UTC)

About locality constraint.. Consider algorithm with following parameters: n=10, m=20, w=5, which means "min(m, i+w)" is always i+w, so DTW[n,m] which is returned by DTWDistance-with-locality-constraint function will always be infinity. So if the algorithm with locality constraint is correct (prooflink?), this should be fixed by "return DTW[n, min(n+w, m)]" or something like this. Antisergey (talk) 11:20, 13 September 2011 (UTC)

Finding an average sequence with regard to DTW has been proven to be hard, but required for many statistical and data mining issues. Should we add something about it? Fpetitjean (talk) 02:44, 21 November 2012 (UTC)

## Obsolete

Please, someone, fix the formatting where it talks about "bold" it doesn't show in the code. — Preceding unsigned comment added by Gforman44 (talkcontribs) 20:46, 5 October 2016 (UTC)

Already fixed.Rgiusti (talk) 13:19, 24 January 2017 (UTC)

Why is DTW[0][0] = 0 in the first algorithm instead of DTW[0][0] = d(s[0], t[0])? -- — Preceding unsigned comment added by 130.149.232.110 (talk) 10:20, 21 October 2014 (UTC)

Series start at s[1] and t[1].Rgiusti (talk) 13:19, 24 January 2017 (UTC)

Probably there is an error in the first algorithm. According to V.Athitsos et al, "Approximate embedding...", section 3.3, equation (8) the first boundary condition should be 0 instead of infinity: DTW[0, i] := 0. I tested this in Matlab, and with this correction it actually produces better results. --Stys (talk) 07:23, 15 June 2010 (UTC)

Series start at s[1] and t[1]. If anything in row or column 0 (except DTW[0,0]) is not infinity, the algorithm will produce out-of-bounds matches.Rgiusti (talk) 13:19, 24 January 2017 (UTC)

## Pseudocode

It isn't clear why return DTW[n, m] is returned, rather than return DTW. —DIV (120.18.188.52 (talk) 09:53, 5 July 2018 (UTC))

## Example

A very simple example with concrete numbers/symbols would be useful. —DIV (120.18.188.52 (talk) 09:54, 5 July 2018 (UTC))