DynamicTimeWarp.jl

Implement Dynamic Time Warping for sequence alignment in Julia.
Popularity
6 Stars
Updated Last
9 Months Ago
Started In
December 2014

DynamicTimeWarp

Build Status

Dynamic Time Warping

A method for aligning sequences in a way that is insensitive to arbitrary "warping" (stretching or shifting) along the time (or "time") axis. Wikipedia article

Features

  • Standard DTW. This algorithm requires O(MN) time and memory, where M, N are the lengths of the two sequences to be aligned.
  • FastDTW (Salvador & Chan, Intelligent Data Analysis 2007), which works by coarsening until DTW is easy, and then stepping back to the finest scales one at a time in a way that lets us search only "a radius" around the best DTW path from the next coarser scale.

To Do List

  • [*] Restricted DTW, where only a parallelogram is explored, not the full rectangular space. (This is a speed/memory optimization.)
  • [*] FastDTW (Salvador & Chan, Intelligent Data Analysis 2007), which works by coarsening until DTW is easy, and then stepping back to the finest scales one at a time in a way that lets us search only "a radius" around the best DTW path from the next coarser scale.
  • [*] Improve FastDTW code by creating a WindowedMatrix type, so that element access can be easier in the dtwwindowed code.
  • Consider implementing SparseDTW paper on arXiv
  • DTW Barycenter Averaging (see paper by Petitjean et al. 2011).
  • Possibly a "spectrum aligner" where the data being warped are histograms. (Does this affect anything? Maybe not needed.)
  • Learn the terminology and actually get proper references in place!
  • Some demonstration examples.