CoreSource checked

Dynamic Time Warping

Measures similarity between sequences that may be stretched or shifted in time.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Intermediate
Family: Sequence Alignment
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 3
Code example: Ready
Visualization: Ready

Overview

Dynamic Time Warping fills a cost table to find a low-cost alignment path between two sequences with flexible timing.

Core Concepts

dynamic programmingwarping pathlocal distancesequence alignment

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n m)

Average

O(n m)

Worst

O(n m)

Space

O(n m)

When to Use

Use when two sequences have similar shape but different timing.
Use when speech pattern matching is a central requirement.

When Not to Use

Avoid when time alignment should remain one-to-one without stretching.
Avoid when the distance or match rule does not reflect the real similarity question.

What It Does

Builds a pairwise distance table
Allows repeated or skipped time positions
Finds a minimum-cost warping path

Use Cases

Speech pattern matching
Gesture recognition
Time-series comparison

Inputs

Two sequences
Point distance function

Outputs

Alignment cost
Optional warping path

Key Formulas (1)

DTW recurrence

dp_[i]_[j] = distance(a_[i], b_[j]) + min(dp_[i−1]_[j], dp_[i]_[j−1], dp_[i−1]_[j−1])

dp[i][j] = distance(a[i], b[j]) + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Chooses the cheapest predecessor for the alignment path.

Pseudocode

1.Create a cost table
2.Initialize the first row and column
3.For each pair of positions, add local distance to the cheapest predecessor
4.Return the final cost and optionally backtrack the path

Canonical Example

Input: a = [1, 2, 3], b = [1, 2, 2, 3]
Output: cost = low
Explanation: The repeated 2 can align with one position in the shorter sequence.

Implementation Notes

Use a Sakoe-Chiba band or another window when long sequences are involved.
Test exact match, no match, repeated characters, and empty input cases.
Keep a tiny example with expected output beside the implementation.

Common Pitfalls

Unconstrained warping can match unrelated regions too flexibly.
Indexing and empty-pattern cases often cause off-by-one errors.
Not defining boundary, empty, or degenerate inputs before implementation.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show an alignment path bending through a matrix between two time series.

Input:ABABABCABAB

Window:ABAB

Step 1 of 4: Create a cost table

sequence-match

Notes

Window constraints can reduce cost and prevent unreasonable alignments.

Sources (1)

What each reference supports for this entry.