Dynamic Time Warping: Aligning Time Series

Why straight-line comparison fails

Two people signing the same word, or two sensors recording the same gesture, rarely move at exactly the same pace. Compare the two recordings point-by-point in time and a tiny lag makes them look nothing alike, even though the shapes are identical. Dynamic time warping solves this by allowing the time axis of one series to stretch and compress locally so that similar features line up, then measuring the cost of the best such alignment.

The cost matrix

Given series X of length n and Y of length m, build an n by m matrix where cell (i, j) holds the cheapest cumulative cost of aligning X up to i with Y up to j. Each cell only needs the pointwise distance between X sub i and Y sub j plus the cheapest of the three neighbouring cells it could have come from - directly above, directly to the left, or diagonally up-left, corresponding to advancing only in Y, only in X, or in both together.

D[0][0] = 0;
for (let i = 1; i <= n; i++) D[i][0] = Infinity;
for (let j = 1; j <= m; j++) D[0][j] = Infinity;
for (let i = 1; i <= n; i++)
  for (let j = 1; j <= m; j++) {
    const cost = Math.abs(X[i-1] - Y[j-1]);
    D[i][j] = cost + Math.min(D[i-1][j], D[i][j-1], D[i-1][j-1]);
  }
// D[n][m] is the DTW distance; backtrack from (n,m) to (0,0) for the warping path

The warping path, and its constraints

Tracing the cheapest route through the matrix, from the top-left corner to the bottom-right, gives the warping path - the actual correspondence between indices of X and indices of Y. Three rules keep the alignment sensible: it must start at (1,1) and end at (n,m) (boundary), it can only move right, down, or diagonally, never backward in either series (monotonicity), and it cannot skip an index in either series (continuity). Together these mean any single point in X can map to several consecutive points in Y and vice versa - exactly the local stretching that fixes the pace mismatch.

Constraining the search: the Sakoe-Chiba band

The unconstrained algorithm above costs O(n times m) in both time and memory, and an unconstrained path can, in principle, warp so aggressively that it produces a technically cheap but semantically meaningless alignment - one very short segment stretched to match a long one. The Sakoe-Chiba band, introduced in the speech-recognition literature, restricts the path to a corridor around the diagonal, a fixed number of steps wide, which both prevents degenerate alignments and cuts computation to roughly O(n times the band width).

Where it is used

DTW distance was central to early speech recognition, where the same spoken word never takes exactly the same amount of time twice. It remains the standard similarity measure for gesture recognition, gait analysis, matching stock-price patterns of different durations, and clustering or classifying time series more generally, usually paired with a nearest-neighbour classifier since the DTW distance itself, not a learned model, is what does the comparison.

Frequently asked questions

Try it live

Everything above runs in your browser - open Dynamic Time Warping and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.