Dynamic Time Warping

Two time series can have similar shape but different timing. A runner may repeat a movement more slowly, or two speakers may utter the same phrase at different speeds. Euclidean distance compares values at matching indices and can report large dissimilarity when corresponding events are shifted. DTW searches for an alignment path through a pairwise cost matrix, allowing one point in one series to align with multiple points in the other. The dynamic programming recurrence accumulates local costs while enforcing monotonic movement through the matrix. A path begins at the first pair and ends at the final pair, with permitted steps such as diagonal, horizontal or vertical advances. The minimum cumulative cost defines the optimal alignment. Implementations report the path cost or its square root and may also normalize by path length, so compare only matching conventions. Constraints such as a Sakoe-Chiba band limit warping to a neighborhood of the diagonal, reducing extreme alignments and computation. For hypothetical motion sequences, a short pause in one performance may align with several nearby frames in another. This can reveal similarity in overall progression despite speed variation. But if warping is unrestricted, unrelated events can be matched by stretching one sequence excessively. A path constraint encodes which timing variation is plausible for the application. Preprocessing, sampling rate, local cost and length normalization all matter. DTW is used in similarity search, time-series classification and clustering. Its standard distance is not generally guaranteed to satisfy the triangle inequality, so metric-tree acceleration assumptions may fail. It can be costly for long sequences, motivating pruning, lower bounds or approximations. Evaluate with labeled examples or domain review, and inspect alignments rather than trusting a single distance. DTW addresses timing elasticity; it does not solve amplitude scaling, missing segments or semantic differences unless those are represented in the local cost or preprocessing. A good alignment is plausible under the allowed path, not proof that two sequences have identical meaning.