DAMP Implementation

[joshualeond]

Hi there, again thanks for Stumpy! I came across this package back in 2019 or so, and to my detriment, I didn't give it nearly as much attention as I should have. Only now, years later, am I realizing the value of the matrix profile.

I see there has been a lot of work on implementing the DAMP (Discord Aware Matrix Profile) algorithm but I don't believe it's finished yet right? Just curious where that work is at or which issues/PRs to follow for progress? The fact that the DAMP algorithm doesn't fall victim to the "twin-freak" problem seems like a huge value-add in anomaly detection.

Thanks again!

[seanlaw]

Hi there, again thanks for Stumpy! I came across this package back in 2019 or so, and to my detriment, I didn't give it nearly as much attention as I should have. Only now, years later, am I realizing the value of the matrix profile.

@joshualeond Thank you for your interest in STUMPY and welcome (back) to our community!

I see there has been a lot of work on implementing the DAMP (Discord Aware Matrix Profile) algorithm but I don't believe it's finished yet right? Just curious where that work is at or which issues/PRs to follow for progress? The fact that the DAMP algorithm doesn't fall victim to the "twin-freak" problem seems like a huge value-add in anomaly detection.

Yes, the DAMP work is being tracked in this issue. Additionally, DAMP can/should be used in MADRID as well. One of the reasons why DAMP is fast (in MATLAB) is that it leverages the mass algorithm which, behind the scenes, uses FFT extensively. Unfortunately, FFT is quite slow in both numpy/scipy so a lot of @NimaSarajpoor's efforts has been focused on writing a faster numba FFT implementation. This is a lot of work but certainly worth it if done "right". FFT is notorious for being hard but I think we are close! Please feel free to subscribe to the first issue above if you'd like to follow its progress.

[joshualeond]

If you end up with an FFT implementation faster than numpy or pyFFTW then that would likely be useful to the OSS community as its own package!

I saw a rather new FFT implementation in Rust named PhastFT that you may find interesting as well. They have some benchmark plots on their Github readme which includes numpy. It looks like they have some python bindings but I'm unsure the effort involved to bring this into your project.

I'll definitely subscribe to the issue and follow along. Thanks!

[seanlaw]

If you end up with an FFT implementation faster than numpy or pyFFTW then that would likely be useful to the OSS community as its own package!

FFTW is certainly the gold standard and also why the DAMP implementation in Matlab is so performant. Of course, FFTW is known to have a ton of custom tweaks to make things fast and, since it's not our forte, we only aspire to come within 2x of FFTW (on average) while attempting to keep things "general". So, our goal is to implement an FFT that is "Fast Enough" while still being easy to maintain.

I saw a rather new FFT implementation in Rust named PhastFT that you may find interesting as well. They have some benchmark plots on their Github readme which includes numpy. It looks like they have some python bindings but I'm unsure the effort involved to bring this into your project.

I think we came across PhastFT as well. However, as a design philosophy, STUMPY has always opted to minimize our dependencies (we only depend on numpy, scipy, and numba) and this choice has served us well (for better or for worse). Of course, if our default "Fast Enough" implementation isn't good enough then @NimaSarajpoor and I have also discussed a simple design that will allow the user to specify their preferred FFT backend (e.g., PhastFT, PyFFTW, etc). That way, STUMPY is not on the hook for dealing with external dependencies. At the end of the day, all we need is to perform a (FFT) convolution so any fft/ifft pair will do.

Please stay tuned!

[joshualeond]

One more question for you on the FFT development in STUMPY: will you need a non-uniform implementation of the FFT to work with irregularly spaced time series or are you able to get around this somehow?

[seanlaw]

Technically, matrix profiles assume that all of the data is equally spaced. However, note that "time" is never actually used in any calculation and so "equal spacing" is assumed but not enforced/checked. Whenever STUMPY receive an array of numbers, we just blindly assume that the data is "correct". Thus, we only require the use of standard FFT algorithms.

To be clear, this is not a STUMPY issue and, instead, is what was described in the matrix profile papers