Understanding the implementation of mStump

[SaVoAMP]

Hey!

I have got another question related to the mStump algorithm.
If I understood everything correctly, mStump should be the same as mStamp - stomp based. While examining the code of mStump I noticed that MASS is used for the distance profile computation (def _multi_mass(Q, T, m, M_T, Σ_T, μ_Q, σ_Q)). I'm a bit confused because I thought that MASS is only used in the Stamp-algorithm and for Stomp they proposed another method in paper 2, where they use the relationship between the dot products of the query with the time series subsequences where they claim that QT_i,j can be computed in O(1) time, once QT_i-1, j-1 is known. They only use the SlidingDotProduct() function for the computation of the first dot product (when i=1 or j=1).
Although they write in their sixth paper ("Meaningful Multidimensional Motif Discovery") at the beginning of page 5:

If the query is selected in a random order, MASS is used for the distance profile computation; otherwise, the method proposed by Zhu et al. (Paper 2) is used for distance profile computation. This is because that method is faster than MASS but requires the subsequences to be selected in order, which nullifies the anytime-algorithm property.

Since Stomp needs in-order evaluation, is there a reason why MASS is used for the multidimensional version of Stomp?

[seanlaw]

I'm a bit confused because I thought that MASS is only used in the Stamp-algorithm and for Stomp they proposed another method in paper 2, where they use the relationship between the dot products of the query with the time series subsequences where they claim that QT_i,j can be computed in O(1) time, once QT_i-1, j-1 is known. They only use the SlidingDotProduct() function for the computation of the first dot product (when i=1 or j=1).

So, believe it or not, you've actually answered your own question. Indeed, mstump utilizes a STOMP-like algorithm. In mstump.py, you see def _multi_mass(Q, T, m, M_T, Σ_T, μ_Q, σ_Q) because it is actually only used to compute the multi-dimensional matrix profile for the first window. After that, it is never used again.

Specifically, in stumpy.mstump, it shows:

stumpy/stumpy/mstump.py

Lines 1000 to 1002 in 5f192a0

	P[:, start], I[:, start] = _get_first_mstump_profile(
	start, T_A, T_B, m, excl_zone, M_T, Σ_T, μ_Q, σ_Q, include, discords
	)

which computes the first mstump profile (i.e., only for the first window for all subsequences) and then this function calls _multi_distance_profile:

stumpy/stumpy/mstump.py

Lines 558 to 560 in 5f192a0

	D = _multi_distance_profile(
	start, T_A, T_B, m, excl_zone, M_T, Σ_T, μ_Q, σ_Q, include, discords
	)

which in turn calls _multi_mass:

stumpy/stumpy/mstump.py

Lines 398 to 406 in 5f192a0

	D = _multi_mass(
	T_B[:, query_idx : query_idx + m],
	T_A,
	m,
	M_T,
	Σ_T,
	μ_Q[:, query_idx],
	σ_Q[:, query_idx],
	)

After the first multi-dimensional matrix profile (for the first window) is computed, then the rest follows a STOMP-like approach to compute the rest of the windows. Notice that _multi_mass is only ever called once at the start of mstump and then never again. Once the process is seeded, the rest completes without calling _multi_mass again. I hope that makes sense.

Since Stomp needs in-order evaluation, is there a reason why MASS is used for the multidimensional version of Stomp?

Consistent with 1-dimensional STAMP/STOMP, MASS is the fastest known approach for computing the matrix profile for a single subsequence window (or the first window). Thus, we've chosen to use the same approach for multi-dimensional matrix profile calculations as well. Unfortunately, the algorithm for mSTOMP is poorly documented and we've gone through a painstaking amount of effort to ensure its validity/accuracy. In my humble opinion, mSTOMP is very easy to get wrong and very hard to get right and STUMPY's goal is to do all of the hard work so that you don't have to.

[SaVoAMP]

Ahh, I didn't understand why exactly MASS is used. The authors only claim that they use the sliding dot product for the first computation. But when looking at the Stomp algorithm again, I notice that lines 2-4 probably correspond to the procedure of MASS:

Am I right?

Unfortunately, the algorithm for mSTOMP is poorly documented and we've gone through a painstaking amount of effort to ensure its validity/accuracy. In my humble opinion, mSTOMP is very easy to get wrong and very hard to get right and STUMPY's goal is to do all of the hard work so that you don't have to.

I very much agree with that! You're doing great work! Unfortunately I need to explain the algorithms Stamp, Stomp and mStamp for my bachelor thesis and right now I don't understand how mStamp really works. They also omit the operations related to storing of the k-dimensional matrix profile subspace completely.

[seanlaw]

Am I right?

Yes, you got it! In my mind, mass is centered around the fast calculation of the sliding dot product and then the dot product is used to compute a distance profile. These two things go hand-in-hand and will always be there to seed/nucleate any STOMP-like process. That is why we call it _get_first_mstump_profile in mstump.py.

For your reference, we've actually included/left in a version of stomp and stamp that should closely resemble the pseudocode in the first two papers. Hopefully, they may serve as a good cross reference but please feel free to ask more questions and I will try my best to explain. In practice, we don't use either of these algorithms because the authors actually published additional papers (using diagonal traversal and GPU implementations) that are even faster than the original version of STOMP that they call STOMPopt. However, for all intents and purposes, it is reasonable to stick to explaining STOMP only as STOMPopt (and its subsequent variants) is really complex but this is also what we evolved in STUMPY.

I very much agree with that! You're doing great work! Unfortunately I need to explain the algorithms Stamp, Stomp and mStamp for my bachelor thesis and right now I don't understand how mStamp really works.

Thank you for your kind words. I think your questions will help others better understand the inner workings of STUMPY and so I am more than happy to answer any further questions that you may have. Please do not hesitate to ask more questions if you have them.

They also omit the operations related to storing of the k-dimensional matrix profile subspace completely.

It took us quite a long time to figure out how this subspace works. Here is a pretty (unstructured but detailed) issue discussion where we eventually figured out what the subspace was and there are some concrete examples that we tried to work through in order to understand what the subspace actually is. Hopefully, that might help you.

In the end, we figured out that it was more practical to re-compute the subspace (on-the-fly after the multi-dimensional matrix profile was computed) for the individual subsequences of interest (i.e., for specific motifs/discords) rather than to store the entire subspace for every subsequence as it was suggested in the paper. Ultimately, this observation is how the stumpy.subspace function was born.

[seanlaw]

In case it matters, please consider citing our STUMPY publication in your thesis

[SaVoAMP]

Yes, of course, I have already done that! 😀