Lag by window in STUMPI

[rnjv]

Hi,

Was looking at STUMPI and found that the matrix profile as designed always lags by its window size. This is not ideal when dealing with realtime or streaming data.

How hard is it to implement this Online Matrix Profile version from this paper: https://www.researchgate.net/publication/354207865_Anomaly_Detection_on_IT_Operation_Series_via_Online_Matrix_Profile/comments

[seanlaw]

Hi @rnjv and welcome to the STUMPY community. Can you provide a concrete example of what you mean? STUMPY follows Page 17 of this paper.

I haven't gone through your paper in detail but it sounds like what you are asking is for the matrix profile to be shifted to the right by the window size. Maybe something like this:

stream = stumpy.stumpi(np.random.rand(100), m, egress=True)
shift_window = np.full(m, np.inf)

for i in range(100):
    t = np.random.rand()
    stream.update(t)
    shifted_left_P = np.concatenate(shift_window, stream.left_P_)
    # Do something with shifted left matrix profile

Would that work?

[seanlaw]

@rnjv Does this answer help?

[rnjv]

What is the difference between stream.P_ and stream.left_P_. Is the matrix profile always of lag m? So is it reasonable to shift the matrix profile by m forward? I am trying to understand as streams arrive at t, are the computed matrix profile an indication of t-m ?

[seanlaw]

What is the difference between stream.P_ and stream.left_P_.

Excellent question. So, stream.P_ is the general matrix profile. This means that for any given subsequence, it is returning the distance to its one nearest neighbor (or for stream.I_, it is returning the index location of its one nearest neighbor). Note that this general matrix profile does not distinguish between whether that nearest neighbor is located to the left (in history) OR to the right (in the future) of the subsequence of interest. This is usually fine when you have the full data in-hand (think batch data). However, typically for streaming data, you don't have access to future information (i.e., data points to the RIGHT) so we tend to only care about stream.left_P_ (or stream.left_I_), which corresponds to the distance to its left nearest neighbor (i.e., the nearest neighbor that is to the left of the subsequence of interest). This ensures that the nearest neighbor for any subsequence can only be matched to a subsequence in the past (relative to the location of a given subsequence) and NEVER to a future (yet-to-be-seen) subsequence. Thus, for stream.left_P_, as each new data point arrives (and creates a brand new subsequence), none of the stream.left_P_ values should ever change (except that it gets shifted by one if egress=True) and the latest subsequence gets assigned a "left nearest neighbor". In contrast, for stream.P_, as each new data point arrives (and creates a brand new subsequence), many of the stream.P_ of the values may change if latest subsequence is "closer" match (to past subsequences) than previously observed.

In summary, for streaming data, it almost ALWAYS makes more sense to use stream.left_P_.

Is the matrix profile always of lag m? So is it reasonable to shift the matrix profile by m forward? I am trying to understand as streams arrive at t, are the computed matrix profile an indication of t-m ?

The goal of STUMPY is to faithfully reproduce the original work published by Keogh et al and, in their papers, each matrix profile distance is ALWAYS aligned with the index location of the first element of each subsequence. For consistency and ease of cross referencing, STUMPY always follows this convention. One may refer to this as a "lag m" and need to shift the matrix profile and matrix profile indices by m but we refrain from doing this to avoid confusion and to minimize assumptions. The user is free to make changes or to leverage the output as they see fit but user is then also responsible for all of the bookkeeping after making a shift. This shifting can be tricky and the user needs to take special care as any off-by-one errors can lead to drastically incorrect interpretations of their results. Does that make sense?

Additional Notes:

1. For any subsequence, if you compute the "left matrix profile" (i.e., left nearest neighbor distance), the "right matrix profile" (i.e., the right nearest neighbor), and then smaller of the two values is actually the "general matrix profile" value (i.e., a "global nearest neighbor"). This is always true for batch matrix calculations like those computed via stumpy.stump. However, for stumpy.stumpi, I refrain from using the word "global" since this may not be true when egress=True (i.e., the nearest neighbor is local to the current observable window).
2. The concept of a "left matrix profile" and "right matrix profile" was first published in Matrix Profile VII paper

[rnjv]

Thank you! This clarifies a great deal. Nice library btw, appreciate the hard work!