Dynamic time warping is an algorithm in time series analysis for measuring similarity between two temporal sequences that may vary in speed, such as detecting similarities in walking even when one person walks faster than the other or accelerates and decelerates. It has been applied to temporal sequences of video, audio and graphics data, with a well known application in automatic speech recognition to cope with different speaking speeds, and other applications including speaker recognition, online signature recognition and partial shape matching; it calculates an optimal match between two sequences under rules that every index of one sequence must be matched to one or more indices of the other, the first and last indices must be matched to each other, and the mapping must be monotonically increasing, warping the sequences non-linearly in time to find the alignment of minimal cost.
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Classification
Design Technique Connections
Sources
1. Dynamic time warping (Wikipedia)
Wikipedia article body, read for Browse By backfill (w-bbfill-computing6-0927)
Dynamic time warping (Wikipedia)
In Group: Edit Distance and Sequence Alignment Algorithms, Lead sectionQuote, In Group: Edit Distance and Sequence Alignment Algorithms, Lead section
algorithm for measuring similarity between two temporal sequences
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.