Add MPdist

[seanlaw]

According to the ICDM publication, the calculation of MPdist is pretty straightforward. For two time series, A and B, of identical length and a window size, m, equal to, say, 50:

1. Compute the matrix profile AB for stumpy.stump(A, m=50, T_B=B, ignore_trivial=False)
2. Compute the matrix profile BA for stumpy.stump(B, m=50, T_B=A, ignore_trivial=False)
3. Concatenate both matrix profiles into PABBA
4. Choose some k that is 5 percent of 2 * n

As mentioned on on page 3 of the above paper, "section, this data structure PABBA
contains all the information we need to compute the MPdist."

The pseudocode can be found here.

The supporting site can be found here

[Deepakgthomas]

I believe after coding the MPDist measure, the development of the Snippet finding algorithm should be relatively simple. I was wondering if your team has any plans to develop it in Python.

[seanlaw]

@Deepakgthomas I think you are correct and, to be clear, there is only one person currently supporting the continued developments so we certainly welcome PRs and we can work with you on this. We’d want to keep the MPdist PR separate from the Snippets PR and consider if it makes sense considering that they’ll be light wrappers around the matrix profile calculation. Currently, MPdist seems like a nice to have but most of it is possible with STUMPY and a little bit of code. What do you think?

With constrained resources, we have to decide whether it is worth supporting the functionality. Also, the key part is ensuring that all new features have 100% test coverage.

_{Sent with GitHawk}

[Deepakgthomas]

I agree with you that there is no immediate need for any additional functions for MPdist, due to the functionality that STUMPY provides.
I would also love to help with the Snippet discovery algorithm, depending upon the time that I have :)

[seanlaw]

Actually, what might be super helpful is if we had a Tutorial notebook that clearly demonstrates how one would compute the MPdist for two time series (preferably, replicating the time series used in the original paper). Then, we could add a snippets Tutorial that references the MPdist tutorial.

That would provide a nice reference implementation if somebody wanted to add it into STUMPY as a set of functions

_{Sent with GitHawk}

[Deepakgthomas]

Sounds good. I will put it on my list of to-dos!

[Deepakgthomas]

Hi Sean,

I've been going over the MPDist paper and I think we need to place in the optimized version of it. This optimized version can be found in the paper (Section III C). The original version won't be of any use during applications (such as snippet discovery). Let me know your thoughts on this.

[seanlaw]

Without digging into it too deeply, I would prefer to have something like MPdist to represent the slow or batch version and MPdistvect to represent the optimized version.
Essentially, the former is batch and the latter is streaming.

In fact, the ingress/egress stuff is essentially done in floss.py (see the floss function where ingress/egress is commented in the code). Note that floss returns a generator and we should/could consider doing the same. I might be inclined to move the common piece of the code out and push it into core.py to remove the redundancy of maintaining the same code in both.

Either way, I’d like for us to start with adding a docs/Tutorial_MPdist.ipynb and reproduce the exact example in the paper. In my experience, there are some subtle nuances that aren’t fully captured in their other papers so this will at least make us more informed.

How does that sound?

_{Sent with GitHawk}

[Deepakgthomas]

Sounds great Sean! Thanks for the clarification.

[seanlaw]

I’ve recently added a new docs/Tutorial_Semantic_Segmentation.ipynb and revamped the docs/Tutorial_Times_Series_Chains.ipynb to what I think are reasonable examples that reproduce key figures and examples from their respective papers. They should serve as a template for what we are looking for except that instead of calling a builtin function, we’d write it out first and then add it into stumpy/mpdist.py afterward.

I will warn you that we have a strict unit testing and code coverage policy for code commits but I can work with you on all of it once we are convinced that the tutorial is correct.

_{Sent with GitHawk}

[seanlaw]

@Deepakgthomas Just checking in to see how things are going and if I could offer any help in this?

[Deepakgthomas]

Apologies for the delay! I should have something by the end of the week.

…

On Tue, Oct 1, 2019, 05:50 Sean M. Law ***@***.***> wrote: @Deepakgthomas <https://github.com/Deepakgthomas> Just checking in to see how things are going and if I could offer any help in this? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#46>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AFHXYWWFJBG2GLQPA2W5WFDQMMTQPANCNFSM4H4R7IYA> .

[seanlaw]

No worries @Deepakgthomas! Let me know if you'd like to bounce anything off of me.

[Deepakgthomas]

Hey Sean,

I just opened up a pull request with my very initial version of MPDist. Could you please have a look at the code? For some reason, I am getting some bugs when I use the stumpy library.

Thank you,
Deepak Thomas