Struct Dtw 

pub struct Dtw<T: Distance + Send + Sync> { /* private fields */ }

Dynamic Time Warping (DTW) algorithm.

Dynamic time warping is 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.

The algorithm is based on the code from the UCR Suite.

Example

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);

Implementations

impl Dtw<Euclidean>

pub fn euclidean() -> Self

Create a new DTW instance using Euclidean distance.

impl Dtw<Manhattan>

pub fn manhattan() -> Self

Create a new DTW instance using Manhattan distance.

impl<T: Distance + Send + Sync> Dtw<T>

pub fn new(distance_fn: T) -> Self

Create a new DTW instance with a custom distance function.

impl<T: Distance + Send + Sync> Dtw<T>

pub fn window(&self) -> Option<usize>

Get the size of the Sakoe-Chiba warping window, if set.

pub fn with_window(self, window: usize) -> Self

Set the size of the Sakoe-Chiba warping window, w.

Using a window limits shifts up to this amount away from the diagonal.

pub fn with_max_distance(self, max_distance: f64) -> Self

Set the maximum distance for early stopping.

During the dtw calculation, if the cumulative distance between two series exceeds this value, the computation will stop and return max_distance.

pub fn with_lower_bound(self, lower_bound: f64) -> Self

Set the lower bound limit for early abandoning.

If the lower bound distance between two series exceeds this value, the computation will stop and return lower_bound.

Multiple lower bounds are calculated and cascaded in order of cheapest to most expensive to compute:

• LB_Kim, a constant time lower bound.
• LB_Keogh, a linear time lower bound.

Generally it is a good idea to set this to the same as the max_distance parameter, as this can speed up the computation by avoiding unnecessary calculations.

pub fn with_upper_bound(self, upper_bound: f64) -> Self

Set the upper bound limit for early abandoning.

If the upper bound on the distance between two series is less than upper_bound, the computation will stop and return upper_bound.

This can be used to speed up the computation by avoiding unnecessary calculations. For example, if the distance matrix is only used for clustering with DBSCAN, we only care if the distance is <= epsilon, so we can stop early if the upper bound is < epsilon.

pub fn parallelize(self, parallelize: bool) -> Self

Set whether to use parallel computation for the distance matrix computation.

This does not affect the computation of individual distances using Dtw::distance, only the computation of the distance matrix using Dtw::distance_matrix.

pub fn distance(&self, s: &[f64], t: &[f64]) -> f64

Compute the distance between two sequences under Dynamic Time Warping.

Example

use augurs_dtw::Dtw;

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

Example with max_distance.

use augurs_dtw::Dtw;

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

pub fn distance_matrix(&self, series: &[&[f64]]) -> DistanceMatrix

Compute the distance matrix between all pairs of series.

The series do not all have to be the same length.

If the parallel feature is enabled and the Dtw instance has been configured to use parallelism using Dtw::parallelize, the calculation is done in parallel.

Example

use augurs_dtw::Dtw;
let dtw = Dtw::euclidean();
let series: &[&[f64]] = &[
    &[0.0_f64, 1.0, 2.0],
    &[3.0_f64, 4.0, 5.0],
    &[6.0_f64, 7.0, 8.0],
];
let dists = dtw.distance_matrix(&series);
assert_eq!(dists[0], vec![0.0, 5.0990195135927845, 10.392304845413264]);
assert_eq!(dists[(0, 1)], 5.0990195135927845);

Trait Implementations

impl<T: Clone + Distance + Send + Sync> Clone for Dtw<T>

fn clone(&self) -> Dtw<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Distance + Send + Sync> Debug for Dtw<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Dtw<Euclidean>

fn default() -> Self

Returns the “default value” for a type.