Talk:Dynamic time warping

Suggested errors and improvments

I think that it would be useful if the formal definition was given, instead of just a code implementation. The code is useful, but it would be easier to understand if the formal definition was given first. Also, it would be useful if there was a formal derivation of the algorithm, with proof given of its various properties.

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 (talk • contribs) 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))

Linear Space Using Hirschberg's Algorithm

There are sources that claim that Hirschberg's algorithm cannot be used to compute the DTW cost in linear space. This claim seems to be wrong as it relies on an example from the paper SparseDTW: A Novel Approach to Speed up Dynamic Time Warping that was calculated wrongly. It is quite clear that one can find a middle node of the optimal warping path and then recurse on the two new subproblems, as it is simply a shortest path problem in a planar grid graph. AnusserWP (talk) 13:29, 17 September 2021 (UTC)

Figure with 2 piecewise linear curves

The figure showing a matching between two piecewise linear curves does not show an optimal matching, since it can be improved by assigning the 4th vertex of the upper curve to the 3rd vertex of the lower curve. (The left ends are counted as 1st vertices).

The illustration should be corrected or removed. AVM2019 (talk) 20:03, 6 September 2022 (UTC)