multivariate stumpy.match

[Emilien1]

Is there any relevance or plan for developing a multivariate version of the stumypy.match method :

stumpy.match : Find all matches of a query Q in a time series T

This is what i am looking for :
[[stumpy.multivariate_match : Find all matches of a query Q in a time series T where Q and T are multivariate timeseries of same dimmensionality.]]

Thanks :)

[seanlaw]

@Emilien1 Thank you for your question and welcome to the STUMPY community. In our library, we have multi-dimensional matrix profile support in mstump (and mmotifs). However, the definition of a multi-dimensional matrix profile is quite different from computing 1-D matrix profiles for each dimension independently and then stacking them on top of each other.

Of course, your question is more about searching for a known multidimensional pattern, Q, in another multidimensional time series, T but without computing any matrix profile. Perhaps I'm missing something but this seems to be analogous to computing the distance profile for each dimension in Q and T and then somehow assessing whether a "match" exists across all dimensions.

Rather than focusing on extending stumpy.match, are you able to provide a concrete example with data regarding what you are trying to accomplish?

[Emilien1]

Hello Sean,
And thank you.
I think you captured the meaning of my question.

The use case is to rapidly scan a multivariate time series T (5 dimensions) for closest k matches given a subsequence Q (5 dimensions) in T.

I was considering performing it in the exact same way that you described : "this seems to be analogous to computing the distance profile for each dimension in Q and T and then somehow assessing whether a "match" exists across all dimensions".

I also wanted to confirm that their is no better (more computationally / mathematically optimized) way to perform such operation as I understand that the mass algorithm is fundamentally for a 1-D serie only.

[seanlaw]

@Emilien1 Thanks for the clarification. According to the original authors, this is indeed the most computationally efficient way to compute the distance profiles since each dimension (and their corresponding distance profile) is 100% independent of the others. The only thing that can be gained is when you compute the the full matrix profile but, again, the "gain" is within each dimension and NOT across dimensions.

Having said that, there is one thing that you need to be aware of. Fundamentally, for a 1-dimensional time series, the distance profile is computed using the mass algorithm (leverages FFT - see the mass function in stumpy/core.py). In STUMPY, this function uses FFT made available via numpy/scipy. However, this means that it is limited by Python's global interpreter lock (GIL) and so you are only able to use a single thread (i.e., core.mass is inherently not multi-threaded). STUMPY has some unpublished/unsupported ways around this but if you're only doing a few Q's (like in the order or 100-1000) then it might not be that bad and you may not need to parallelize the process. However, as T gets larger, and you have more than 1000 Q's in which to generate the distance profile for then you may want to consider alternatives to help parallelize it.

Again, it's hard to make any recommendations without knowing more details.

[Emilien1]

Thanks @seanlaw for the clarification this answered my question.

[Emilien1]

For information in one of the matrix profile foundation paper they also make mention in a 2D case of adding the two profiles together before finding the minimum value for the match on the resultant profile vector. I guess this is all dependent on the use case and level of conservatism required.

[NimaSarajpoor]

@Emilien1 @seanlaw
If you do not mind, I would like to share my idea on this one. I was scrolling and the term "multivariate" got my attention.

---

If I understand correctly, you want to create a 1D-distance profile of (query Q, time series T) as you want to see patterns (motifs) across all dimensions that start from the same index.

If that is the case, then, as @seanlaw mentioned, mass algorithm can be used to find distance profile of 1-dim query Q and all subsequences of 1-dim T. So, after getting distance profile in each dimension, you may want to calculate the square root of their sum of squares. (However, you can also just add them. This is similar to a case where you have some features and your distance between two data points can be L1 norm or L2 norm. Here, each feature is one dimension in your case). Now, you have a distance profile between Q and T considering all dimensions together. You can then find smallest distance to Q (be careful to exclude trivial neighbors).

(Just for the record: to construct "matrix" profile, you can just consider each subsequence of T as query, then you iterate through all subsequences in T. So, in iteration i, where Q = T[i: i+m], you will get its corresponding distance profile, which gives you the value of P[i], where P is matrix profile.)

---

NOTE:
Since your data is multi-dim time series, you should be careful as one of them might dominate..so I think setting input normalize = True (in function mass) should be fine. However, if you want to put normalize=False, it might be a good idea to normalize the WHOLE sequence T in each dimension first (e.g. you can do standardization or min-max scaling). And, maybe use the same scaling parameters to scale Q. (similar to classification case: where you first standardize your train set and then you standardize your test set based on the scaler fitted to train set)

---

If you are planning to extend your research in the future, one idea is to consider Dependent-DTW [1] (which consider simultaneous time shift across all dimension.) There is an open issue ( see #466 ) in STUMPY for implementing DTW-based matrix profile. However, in your case, if you think there is a dependency between dimensions, you should think of extending it to Dependent-DTW. (It can be a good paper as you need to come up with its algorithm first!)

[1] Shokoohi-Yekta, Mohammad, et al. "Generalizing DTW to the multi-dimensional case requires an adaptive approach." Data mining and knowledge discovery 31.1 (2017): 1-31.

[NimaSarajpoor]

@Emilien1
The picture you provided for 2D case has some interesting notes on this topic! They said one of the caveats is that you may need to consider different weights when combining distance profile. This is not just for matrix profile. You can say the same thing for unsupervised learning. If I give you data with 2 features, the common approach is to standardize each feature. But, you may want to consider different scales. So, that caveat has its root in the definition of similarity. So, do not worry about that part. However, as I said, you need to be careful to not let one feature (i.e. dimension in your case) dominates. If you have some labels that can say if the match you discovered is correct, then yes....you can think of those weights as hyper parameters.

[Emilien1]

Hello Nima and thank you,

You correctly understood the idea.
These are interesting insights.

I have also considered at first place a resultant distance profile vector as the square root of their squared sum on each dimension. Ultimately there is no best method, the engineering of the “combined” score / distance will depend on the use case and the behavior researched for multidimensional match occurrence.

In my particular use case having the match on each dimension (the minimum distance defined independently for each dimension) is the best way forward (more conservative / less tolerance for a mismatch on one dimension). I took care of possible shifting / lag with some different approach to give a tolerance zone which is proportional to the query length.