Clarification on documentation: does stumpy.match rely on MPDist?

[patrickfleith]

I would like to understand better how the methods stumpy.match and stumpy.mass compute the distance under the hood to find the best matches. I assume it relies on the measure MPDist but it is not explicitly mention in the documentation which distance measure it uses. Could you clarify?

[seanlaw]

Hi @patrickfleith! Welcome to the STUMPY community and thank you for your question.

I would like to understand better how the methods stumpy.match and stumpy.mass compute the distance under the hood to find the best matches. I assume it relies on the measure MPDist but it is not explicitly mention in the documentation which distance measure it uses. Could you clarify?

No, stumpy.match uses stumpy.mass to compute the distance under the hood. For all intents and purposes, stumpy.mass is just a fast way (leveraging FFT) to compute the sliding window dot product between the query subsequence, Q, and all subsequences within your time series, T. Once the dot products are computed, it is trivial to compute the correspodning (z-normalized) Euclidean distance(s). I recommend looking at this paper to better understand the inner workings. At the end of the day, it computes the (z-normalized) Euclidean distance and that is all you should need to care about.

To be explicit, stumpy.match and stumpy.mass do not use MPdist and is mostly unrelated. I hope that helps.

[patrickfleith]

Great, many thanks. And from what I observe there is no other routine which search for the best matching based on MPDsit, right? One would have to come up with his.her own search function?

[seanlaw]

Great, many thanks. And from what I observe there is no other routine which search for the best matching based on MPDsit, right? One would have to come up with his.her own search function?

That is correct. At the end of the day, you are computing a "distance" and then it is up to you to set a distance threshold that decides whether something is "significant" or not.

[patrickfleith]

Ok great thanks I close the issue

[seanlaw]

@patrickfleith In the future, would you mind posting usage questions to our Github Discussions? This way, others may chime in and provide their perspective too.

[NimaSarajpoor]

@patrickfleith
I am late to the party, but please allow me to share my opinions with you. As @seanlaw mentioned, the distance measure/metric and the threshold is up to you. At the end of the day, we need that to find the best matches.

I think stumpy is designed in a way that you can usually find a way to (easily?) build what you are looking for. Here is what I think you can do to get what you want. (I haven't tried it but you can play with it and you may get what you are looking for)

Let's start with function match in stumpy/motifs.py:

stumpy/stumpy/motifs.py

Lines 354 to 367 in 92ef4d5

	def match(
	Q,
	T,
	M_T=None,
	Σ_T=None,
	max_distance=None,
	max_matches=None,
	atol=1e-8,
	query_idx=None,
	normalize=True,
	p=2.0,
	T_subseq_isfinite=None,
	T_subseq_isconstant=None,
	):

So, this takes Q and T as the input, and then find the distance between Q and all subsequences of T, using mass algorithm. If you check out the function match, you can see this block of lines:

stumpy/stumpy/motifs.py

Lines 488 to 493 in 92ef4d5

	D = np.empty((d, n - m + 1))
	for i in range(d):
	D[i, :] = core.mass(
	Q[i], T[i], M_T[i], Σ_T[i], T_subseq_isconstant=T_subseq_isconstant[i]
	)
	D = np.mean(D, axis=0)

As shown above, in line 490, function mass is used. As a side note, notice that the index i is NOT the index in a time series, but instead, it is the index of dimension when you have multi-dimensional data. In most cases, data is 1D, and so, d==1 , and hence for i in range(d) is basically one iteration.

Okay...let's get back to the main point. Now, instead of mass, you should be able to use any function that takes input Q and T and return their distance profile. (for more info on this, take a look at the function mass and its doctoring). Now, all you want is to replace this with a function that is based on mpdist (I think that should work. right?).

Fortunately, stumpy supports this part of puzzle as well. If you take a look at function _mpdist_vec in stumpy/mpdist.py, you can see the following:

stumpy/stumpy/mpdist.py

Lines 166 to 179 in 92ef4d5

	def _mpdist_vect(
	Q,
	T,
	m,
	μ_Q,
	σ_Q,
	M_T,
	Σ_T,
	Q_subseq_isconstant,
	T_subseq_isconstant,
	percentage=0.05,
	k=None,
	custom_func=None,
	):

Based on my understanding, this function calculates the distance between Q and all subseqs of T (similar to mass) and the distance between Q and each subsequence is actually MPDIST.

[patrickfleith]

@NimaSarajpoor Thanks for your great feedback. Indeed this sounds like a good way to implement what I was looking for. Thank you, I'll post the outcomes when I get back to it.

And just to give a bit more context to readers of this thread, the reason why I was asking this: it is because the MPDist measure has some properties that the euclidean distance doesn't (some extra invariances).