Dynamic Time Warping (DTW)

Implementation of the dynamic time warping (DTW) algorithm.

DTW can be used to compare two sequences that may vary in time or speed. This implementation has built-in support for both Euclidean and Manhattan distance, and can be extended to support other distance functions by implementing the Distance trait and using the Dtw::new constructor.

Features

• DTW distance between two sequences
• optimized scalar implementation influenced by the UCR Suite
• SIMD optimized implementation
• Z-normalization
• distance matrix calculations between N sequences
• parallelized distance matrix calculations
• early stopping using LB_Kim (semi-implemented)
• early stopping using LB_Keogh (semi-implemented)
• early stopping using the Euclidean upper bound

Pull requests for missing features would be very welcome.

Usage

use augurs::dtw::Dtw;

let a = &[0.0, 1.0, 2.0];
let b = &[3.0, 4.0, 5.0];
let dist = Dtw::euclidean().distance(a, b);
assert_eq!(dist, 5.0990195135927845);

Credits

The algorithm is based on the code from the UCR Suite. Benchmarks show similar or faster timings compared to dtaidistance's C implementation, but note that dtaidistance is much more full featured!

License

Dual-licensed to be compatible with the Rust project. Licensed under the Apache License, Version 2.0 <http://www.apache.org/licenses/LICENSE-2.0> or the MIT license <http://opensource.org/licenses/MIT>, at your option.