Stumpy and Dynamic Time Warping

[evoisec]

When e.g. identifying frequent motifs (including in multidimensional timeseries) or doing A-B joins between two time series based on similar motifs, does stumpy / the ts matrix profile perform Dynamic Time Warping as described here (from the same same researches who invented the matrix profile https://www.cs.unm.edu/~mueen/DTW.pdf)

concrete example - lets say we are looking for motifs of length 10 (sliding window of 10 time series data points) - however in one 10 points segment the same motid/shapelet is expressedwith 6 out of the 10 poiunt sliding window in another with 9 etc but the shape of all of them is similar - to match/align such motifs, there should be some DTW going on under the hood - is that part of the implementation of Stumpy/the matrix profile or it relies on/requires point for point matching for the entire sliding window ?

[seanlaw]

@evoisec Thank you for your question and welcome to the STUMPY community.

does stumpy / the ts matrix profile perform Dynamic Time Warping

No, currently, STUMPY does not perform DTW. However, DTW-based matrix profiles has already been proposed in issue #466. Note that efficient implementations of DTW is non-trivial and requires quite a bit if knowledge on the subject. Contributions are welcome. I hope that helps.

[evoisec]

Thank you Sean

in terms of time efficiency this paper from the very same researchers behind the time series matrix profile claims that there are some breakthroughs moreover apparently based on the matrix profile too https://www.cs.unm.edu/~mueen/DTW.pdf

so to recap, the current implementation matches and compares timeseries data points index for index (so to speak) to discover morifs etc and there is no use of a more flexible / less rigid Dynamic Time Warping for aligning/realigning and matching sequences?

[seanlaw]

Yes, that is correct. As evidenced by the 100+ slides, implementing an efficient DTW is non-trivial.

[jacktang]

hello @seanlaw , did you notice fastDWT https://cs.fit.edu/~pkc/papers/tdm04.pdf? from the benchmarks, it seems promosing.

[seanlaw]

@jacktang Thank you for your question. According to the original authors of the matrix profile (Eamonn Keogh), fastDTW is "generally slower than the algorithm that it approximates":

https://arxiv.org/abs/2003.11246

[jacktang]

Wow, thanks for the sharing

[Landcruiser87]

DTW always looks promising. Until you wait for it to finish ... and wait. and wait. This is why nobody uses it. Time complexity of O(n*m) is a killer

[evoisec]

unfortunately the real world / real world problems (at least most of them) require DTW (btw performed seamlessly by the brain) .....

matching timeseries data points index for/by index to find motifs etc is a too "idealized" setup which requires everything to be aligned perfectly but the real world is anything but perfect including man made world like capital markets etc

ps: also, although the matrix profile is not "AI", the above is also indicative why all current "AI" is far from what a brain can do in relation to the "real world"