Sktime: Implement AWarp distance measure

[big-o]

Is your feature request related to a problem? Please describe.
AWarp is a variant of Dynamic Time Warping for sparse time series. It claims to be exact for binary-valued series and a close approximation for continuous-valued series. DTW can be prohibitively slow for large, sparse series and series which are unaligned (which leads to a sparse DTW matrix). In these cases, AWarp may provide something more feasible.

Describe the solution you'd like
Implement a new distance metric, 'awarp', that can be used in place of existing metrics when desired. Would it also be a good idea to fall back onto awarp automatically if dtw is requested but a high degree of sparsity is detected in the DTW matrix?

Describe alternatives you've considered
The only alternative I'm aware of is FastDTW, but AWarp claims to be much more performant (for sparse series at least).

A Python implementation now exists here: https://github.com/mclmza/AWarp. It uses Numba to further speed things up. Given how small the code is though, it could be easier to re-implement than wrap. It looks like this implementation uses dense matrices and iteration, so maybe some further improvements could be made by using sparse containers and (if possible) broadcasting.

I'm aware there is a discussion ongoing around data containers, so the best way to implement AWarp could depend on the outcome of this.

Additional context
The original paper, test datasets and an implementation in C++/Matlab can be found here.

[fkiraly]

This also raises an interesting question about event series, i.e., data which are the occurrence times of events.

AWarp is a kernel where vanilla inputs are event series, then applying a natural transformer which represents an event series as the sequence of inter-event-durations - which is separate from what you do after, and useful in isolation.

The second part of AWarp looks like it could be useful for any sequence of non-negative integers (or perhaps even reals).

@TonyBagnall or @jasonlines (with their view of the field) might be also able to comment better on whether AWarp is a simple composite of the aforementioned transformation and, say, a warping distance we have already implemented somewhere.

[TonyBagnall]

hi, thanks for that. We have a load of alternative distance measures in development with these folk
https://arxiv.org/abs/1806.04509
which next year we will do an evaluation with. @goastler is working on it.

AWarp has not made it in yet, we have concentrated on equal spaced versions, but I am aware of it. Is that Mueen's implementation? If so, I'll ask him if he wants to get involved porting it in, spoke to him earlier in the year and he was up for collaboration ... at least thats how I remember it if your reading this Mueen :) Always good to have the initial authors involved.

Also, we may consider including Numba as I believe it is required by another algorithm, ROCKET.

[fkiraly]

Well, technically, after applying the transform to waiting times, you can consider the series equally spaced (it's just a sequence), although you may end up with different length.

[big-o]

Is that Mueen's implementation?

Yes - and I haven't compared the Python implementation in detail but it looks to be pretty much a straight copy of the original Mueen code.

[TonyBagnall]

@big-o thanks for raising this, Mueen is keen to collaborate and his student Sheng Zhong is going toi port it in. If you also want to contribute to this sub project I'm sure there will be room! I'll set up a slack channel for those interested to join

[big-o]

Thanks @TonyBagnall - it'll be great to finally have a solid and simple-to-use Python implementation. It sounds like you already have enough contribution effort for this so I wouldn't want to be the cook that spoils the broth, and I'm sure the authors can do a far better job of implementing this than me! I've also offered to help out on some time series classification work so I would probably be spreading myself too thin by getting involved in anything else right now. I'd be very interested in any updates to this though.