Feature Request: Multidimensional DTW?

[par5er]

One of the most common use cases for DTW is to compare two MFCC streams. These usually have the shape (n_frames, n_coefficients_per_frame) where n_coefficients_per_frame is below 13-20. However, augurs-dtw only accepts 1D input vectors. Could this library add support for 2D vectors as well? Thank you

[sd2k]

Hey @par5er, do you have an example implementation from e.g. Python?

I don't have a use for this personally so doubt I will implement it myself, but may consider a PR if it's suitably time-series focused.

[par5er]

The distance method just has to be changed to accept both 1D and 2D sequences:

augurs/crates/augurs-dtw/src/lib.rs

Line 262 in f5becde

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

And implement Euclidean distance for &[f64] (inner arrays)

augurs/crates/augurs-dtw/src/lib.rs

Line 22 in f5becde

fn distance(&self, a: f64, b: f64) -> f64;

For Dtw::distance, I think a generic allowing any Distance-implementing type instead of hardcoded &[f64] should do the trick. This might be a breaking change, though

Here's a pure Python implementation (as you can see, the only extra step is a Euclidean distance over the inner arrays): https://github.com/slaypni/fastdtw/blob/ea13ae2e6761f056623ff1d3ac6c71fcf4f94497/fastdtw/fastdtw.py

[sd2k]

Ah interesting, that's simpler than I thought, thanks. It sounds like we would need Euclidean to be a trait here that we could implement for f64 and &[f64]. That would probably require a bit of type gymnastics, but I think it would work fine. Happy to review a PR to add this!

[par5er]

Hi sorry about the slow response. I'll work on the PR shortly

[sd2k]

Awesome, thanks!