Understanding the exclusion zone for very large window sizes

[giacomoguiduzzi]

Greetings,

I was trying to understand this on my own but I'm having difficulties, so I thought of asking here. I have a kind of big Time Series (around 464k points) and I was trying to identify motifs using some default time values (for example 1 hour, 3 hours, 1 day, 1 week etc.). When running stumped (the dask parallelized implementation) I noticed that using a very big value of m (e.g. 432000) causes the diagonal array to be empty:

(stumped.py:622)

ignore_trivial = core.check_ignore_trivial(T_A, T_B, ignore_trivial)

n_A = T_A.shape[0]
n_B = T_B.shape[0]

excl_zone = int(np.ceil(m / config.STUMPY_EXCL_ZONE_DENOM))

if ignore_trivial:
    diags = np.arange(excl_zone + 1, n_A - m + 1, dtype=np.int64) <-- returns {np.ndarray: (0,)} []
else:
    diags = np.arange(-(n_A - m + 1) + 1, n_B - m + 1, dtype=np.int64)

To fix this I think I should increase the value of STUMPY_EXCL_ZONE_DENOM, but I'm not sure why this happens and why it isn't handled. Since I'm running the stumped function on a single Time Series, the ignore_trivial parameter is set to True. If I set it to False and pass my Time Series twice both as T_A and T_B, then everything works correctly.
My question is: is this normal or is it a corner case that leads to a bug? If it is a bug I'd gladly try to understand why this happens and create a PR, if it can be of use. If it's expected, can you please explain why so to get a better understanding of the algorithm?

Thanks in advance!

Best Regards,
Giacomo Guiduzzi

[seanlaw]

@giacomoguiduzzi Can you please provide a minimum reproducible example with T = np.random.rand(464_000) and then show how you are calling stumped to produce this problem?

[giacomoguiduzzi]

Hi @seanlaw and @NimaSarajpoor,
Sorry for the delay. What Nima suggested is exactly what happens. The values of n_A, m, and excl_zone are 464349, 432000, and 108000.
I wanted to suggest raising a warning to let the user know that the condition for the exclusion zone is not satisfied, thus the matrix profile cannot be computed normally (with "normally" I mean that it is necessary to perform the other calculation that is in the else branch).

Here is a small reproducible example:

import numpy as np
import stumpy
from dask.distributed import Client


def main():
    ts = np.random.rand(464_349)
    m = 432_000
    with Client() as dask_client:
        matrix_profile = stumpy.stumped(dask_client, ts, m=m)


if __name__ == "__main__":
    main()

I'm at your disposal.

Thanks once again,
Giacomo Guiduzzi

[seanlaw]

@giacomoguiduzzi We are deciding on the right verbiage for the warning in issue #1077.

I wanted to suggest raising a warning to let the user know that the condition for the exclusion zone is not satisfied, thus the matrix profile cannot be computed normally (with "normally" I mean that it is necessary to perform the other calculation that is in the else branch).

Respectfully, I disagree that one should use the else path. For self-joins, it rarely (if ever??) makes sense to ignore trivial matches (i.e., subsequences matches that are inside of the exclusion zone). The only time you could/should set ignore_trivial=True is when performing an AB-join (i.e., computing a matrix profile between two different time series). Otherwise, in the self-join, you'll end up matching yourself! Instead, for self-joins, you can either decrease your window size, m, OR increase config.STUMPY_EXCL_ZONE_DENOM. However, in the latter case, altering that value may be dangerous unless you really know what you are doing (so it is not recommended). Basically, setting config.STUMPY_EXCL_ZONE_DENOM = np.inf would turn off any exclusion zone, which for 99.99% of cases would be a bad idea and not something that we support.

[giacomoguiduzzi]

Thanks for clarifying that @seanlaw, no need to to be so formal about disagreeing. I only suggested that edit because the else branch worked in place of the if branch for that specific case, but I had no idea about its correctness for self-joins. I apologize for not being clear on that aspect. I do agree with you that it would lead to errors, now that I have a better idea of how it works!
I'm looking forward to your response about the script whenever you have the time to try it out.

Best,
Giacomo Guiduzzi

[seanlaw]

I'm looking forward to your response about the script whenever you have the time to try it out.

As discussed in issue #1077, the problem that you are encountering is that the m must be smaller than or equal to n - excl_zone (note that excl_zone = int(np.ceil(m / config.STUMPY_EXCL_ZONE_DENOM)). If this is violated, then you will never get any valid nearest neighbor matches. In your case, m is simply too large to return any valid nearest neighbor (i.e., all subsequences are eliminated either because they are residing within the exclusion zone of the ith subsequence or because all other remaining subsequences (near the start/end of the time series) are too short (i.e., shorter than m) and are therefore invalid).

Let's use your example where len(ts) == 464_349, m == 432_000, and therefore excl_zone == 108000. Imagine if we were looking for the nearest neighbor for the very first subsequence located at index i = 0 (i.e., ts[0 : m]). First, we invalidate all subsequences that reside within the exclusion zone of ts[0 : m]. This means that all subsequences that have start index in j <= 108000 are "invalidated". Now, the question becomes, "what subsequence start indices, j, still remain?" Let's look at the obvious "next" start index value of j == 108001 (i.e., ts[108001 : 108001 + m]), which is the first available index value right outside of the exclusion zone. But where does this subsequence end (i.e., what is 108001 + m)? Well, 108001 + m == 540_000. In other words, the "end" has travelled past the end of your time series (remember that len(ts) == 464_349!!). In fact, every single subsequence will be too short (i.e., they will all have a length that is shorter than m and are therefore invalid subsequences). Therefore, for m == 432_000, you will NEVER have ANY valid nearest neighbor subsequences because your window size is too large (or your time series is too short). In other words, there is nothing to do and no matrix profile to compute.

[giacomoguiduzzi]

Hi @seanlaw ,

Sorry for the delay. I get it now; thank you very much for your precision and clarity. I was expecting a warning or an exception to be raised if something like that happened, thus the confusion.
I hope this explanation helps others who have the same doubts. :)

Best Regards,
Giacomo Guiduzzi

[seanlaw]

I get it now; thank you very much for your precision and clarity

You are most welcome!

I was expecting a warning or an exception to be raised if something like that happened, thus the confusion.

You're absolutely right! Based on your question and feedback, we are working on detecting this problem and will be adding a warning in this issue.