[MNT, ENH, DOC] Rework similarity search

[baraline]

Reference Issues/PRs

Fixes #2341, #2236, #2028, #2020, #1806, #2475, #2538

What does this implement/fix? Explain your changes.

The previous structure for similarity search was not in line with the structure we would expect considering other aeon modules, the lack of distinct base classes for some tasks, as well as the initial design choice (due to the lack of practical experience with using and expanding the module) lead to some really complex code when working on #2341 to make everything work together. Further expanding the module would have made thing worse.

To make the module more flexible and comprehensible, the following rework is proposed in this PR (AEP to be updated acordingly):

The module structure is now :

|-similarity_search
|------series
|------------neighbors #NN on subsequences 
|------------motifs #Motif extraction on subsequences methods
|------collection
|------------neighbors # series methods for subsequence NN adapted to collection case or Approximate NN on whole series
|------------motifs #Series methods adapted to collection case

Base classes are BaseSimilaritySearch, BaseSeriesSimilaritySearch, BaseCollectionSimilaritySearch Implemented estimators are :

• (series/neighbors) MassSNN : subsequence nearest neighbors and distance profile computation
• (series/neighbors) DummySNN : brute force subsequence nearest neighbors
• (series/motifs) StompMotifs : top k motifs extraction (supports motifs pairs, k-motif or r-motifs)
• (collection/neighbors) RandomProjectionIndexANN: Approximate nearest neighbors on whole series using a random projection LSH method.

The sufix of the estimators (SNN/ANN/Motifs) remains an open discussion, not sure it's the right way to go.

I removed the support for collections for Stomp and Mass for now to focus on the "expected and well known" use cases, I'll make them in another PR.

All similarity search estimators now use fit/predict interface, with predict returning two arrays (NN/Motifs indexes, and NN/Motifs distances).

Does your contribution introduce a new dependency? If yes, which one?

No.

Any other comments?

As this is still a WIP, I would love some inputs on the structure (notably from @patrickzib !) to make the module more future-proof to future additions and easier to use.

TODO list :

• [x] Finish to include testing suite for base estimators in the testing module for the SubsequenceSearch part and fix them
• [x] Implement LSH index as a simple first case for BaseCollectionSimilaritySearch
• [x] Implement tests for base classes and estimators
• [x] Update API docs / doc pages
• [x] Update notebooks
• [x] Check docstrings
• [x] Cleanup TODOs in the code
• [x] updated aeon's CODEOWNERS to receive notifications about future changes to these files.

[aeon-actions-bot[bot]]

Thank you for contributing to aeon

I have added the following labels to this PR based on the title: [ $\color{#F3B9F8}{\textsf{documentation}}$, $\color{#FEF1BE}{\textsf{enhancement}}$, $\color{#EC843A}{\textsf{maintenance}}$ ]. I have added the following labels to this PR based on the changes made: [ $\color{#006b75}{\textsf{similarity search}}$ ]. Feel free to change these if they do not properly represent the PR.

The Checks tab will show the status of our automated tests. You can click on individual test runs in the tab or "Details" in the panel below to see more information if there is a failure.

If our pre-commit code quality check fails, any trivial fixes will automatically be pushed to your PR unless it is a draft.

Don't hesitate to ask questions on the aeon Slack channel if you have any.

PR CI actions

These checkboxes will add labels to enable/disable CI functionality for this PR. This may not take effect immediately, and a new commit may be required to run the new configuration.

• [ ] Run pre-commit checks for all files
• [ ] Run mypy typecheck tests
• [x] Run all pytest tests and configurations
• [ ] Run all notebook example tests
• [x] Run numba-disabled codecov tests
• [ ] Stop automatic pre-commit fixes (always disabled for drafts)
• [ ] Disable numba cache loading
• [ ] Push an empty commit to re-run CI checks

[patrickzib]

Thank you very much for working on this.

Some thoughts:

• Focus the module on two distinct tasks : find_neighbors and find_motifs for all type for similarity search estimators. Similarly to the fit/ predict interface we already know well, here, we first fit and then either find_motifs or find_neighbors ("predict" keyword don't make much sense here). We give a collection to use as database in fit, and a single series in find_neighbors or find_motifs to use as query for the search.

That is an interesting problem. Here is my view:

For whole series similarity search fit requires a dataset of time series of equal length, and find_neighbors would get one or many query series of this length.

For subsequence similarity search fit requires a single time series, and find_neighbors commonly gets a single query sequence which length is shorter than the single series length. It would be fine however, to extend it to multiple short sequences.

There is only one whole series consensus motif search paper, which would be the use case of whole matching and motif discovery. The input to fit would be the whole dataset, and find_motif has no input series X. not sure, what an input series X should trigger.

Most papers solve the problem of motif discovery in a single long time series, defined as subsequences of the time series. Here, fit gets a single series, and find_motif has no input series X.

• Distinguish between two kind of similarity search tasks with the two submodules, SeriesSearch and SubsequencesSearch. The SubsequencesSearch focuses on tasks for which the goal is to find motifs or neighbors in subsequences of time series (e.g. Matrix Profiles, Motiflets, etc.). the SeriesSearch focuses on task using whole series (e.g. Indexes such as LSH, iSAX, etc.)

• Have base classes for families of method to limit code duplication (e.g. BaseMatrixProfile, and STOMP, where most existing code was ported), so the we can focus on implementing the computational logic when adding new estimators.

What is the difference between BaseMatrixProfile and STOMP?

At least for Motiflets, we cannot use STOMP/MP, as it only gives a 1-NN profile, but we need k-NN profiles. Same problem would be the case, if you want to solve k-nearest neighbors similarity search.

Questions to answers for motif search :

• Do we want to make providing X optional in find_motifs ? Providing X means that we search for subsequences in X that are motifs in the collection given in fit. Not providing X would mean that we search for motifs in the collection given in fit only. I think it would make sense to make it optional, but would love some comment from people actually doing motif discovery.

I think that X is not meaningful for motif discovery.

[baraline]

Thanks for the inputs @patrickzib😄

For whole series similarity search fit requires a dataset of time series of equal length, and find_neighbors would get one or many query series of this length.

Completely in line with this, but what about the case of unequal length series, with, for example, elastic distance measures? Wouldn't that be a plausible use case? (all whole series estimators don't have to support it)

For subsequence similarity search fit requires a single time series, and find_neighbors commonly gets a single query sequence which length is shorter than the single series length. It would be fine however, to extend it to multiple short sequences.

For this case, I'm defining a length parameter during __init__, and accept a 2D subsequence of shape (n_channels, length) for find_neighbors, ensuring that length is not bigger than the length of any series given in fit. However, any reason why you think we should restrain ourselves to a single series for fit ?

There is only one whole series consensus motif search paper, which would be the use case of whole matching and motif discovery. The input to fit would be the whole dataset, and find_motif has no input series X. not sure, what an input series X should trigger.

This is the tricky one for me too. I'm not sure how giving X during find_motifs on whole series would fit any use case.

Most papers solve the problem of motif discovery in a single long time series, defined as subsequences of the time series. Here, fit gets a single series, and find_motif has no input series X.

I've been kinda frustrated by this limitation for practical use cases, wouldn't it be fine to loop on series of a collection with the motif discovery methods and then merge the results ? That's how I implemented STOMP for now for example. For each subsequence in X, it computes the distance profile to all series in a collection, and keep the top k among all of them (also storing the sample ID and timepoint ID).

What is the difference between BaseMatrixProfile and STOMP? At least for Motiflets, we cannot use STOMP/MP, as it only gives a 1-NN profile, but we need k-NN profiles. Same problem would be the case, if you want to solve k-nearest neighbors similarity search.

BaseMatrixProfile (which inherit BaseSubsequenceSearch) is simply a base class that defines abstract compute_matrix_profile and compute_distance_profile methods to be implemented by child classes such as STOMP and the likes (STUMP, etc...). The logic for finding neighbors / motifs is then handled in the BaseMatrixProfile. I wanted to leave the door open to alternative methods and not just focus on matrix profiles, hence the split.

As stated above, I already extended STOMP to support k-NN profiles for collections (multivariate and unequal length compatible).

I suppose that in this context, motiflets would either inherit from BaseMatrixProfile if you need to implement methods like compute_matrix_profile and compute_distance_profile. Otherwise, It would inherit from BaseSubsequenceSearch and make its own methods to answer the find_neighbors/find_motifs tasks. (I would need to read the paper again!)

Note that it's possible to simply raise a "NotImplementedError" or something similar if an estimator would only support neighbors or motifs search.

My goal here is to find a base class structure that enables us to move most common code to there and focus on the computational optimisations of each method in the child classes.

I think that X is not meaningful for motif discovery.

In the context of motif search in a single series I agree, but wouldn't there be some interest when dealing with a collection ? For example find motifs in the collection at the condition that they are similar to a subsequence in X ? (This is pure speculation)

[patrickzib]

Completely in line with this, but what about the case of unequal length series, with, for example, elastic distance measures? Wouldn't that be a plausible use case? (all whole series estimators don't have to support it)

Sure. I did not think of this.

For subsequence similarity search fit requires a single time series, and find_neighbors commonly gets a single query sequence which length is shorter than the single series length. It would be fine however, to extend it to multiple short sequences.

For this case, I'm defining a length parameter during __init__, and accept a 2D subsequence of shape (n_channels, length) for find_neighbors, ensuring that length is not bigger than the length of any series given in fit. However, any reason why you think we should restrain ourselves to a single series for fit ?

Simplicity :) But I agree that you could have multiple series in fit, too - this would mimic the Shapelet use case, I suppose?

Most papers solve the problem of motif discovery in a single long time series, defined as subsequences of the time series. Here, fit gets a single series, and find_motif has no input series X.

I've been kinda frustrated by this limitation for practical use cases, wouldn't it be fine to loop on series of a collection with the motif discovery methods and then merge the results ? That's how I implemented STOMP for now for example. For each subsequence in X, it computes the distance profile to all series in a collection, and keep the top k among all of them (also storing the sample ID and timepoint ID).

Sorry, yes, that is what the authors refer to as consensus motif: https://www.cs.ucr.edu/~eamonn/consensus_Motif_ICDM_Long_version.pdf

BaseMatrixProfile (which inherit BaseSubsequenceSearch) is simply a base class that defines abstract compute_matrix_profile and compute_distance_profile methods to be implemented by child classes such as STOMP and the likes (STUMP, etc...).

I see. I personally do not like to use the terms matrix-profile for simple k-NN distances or k-NN indices though. It was a brilliant re-framing of EK, such that all 1-NN algorithms are now suddenly an instance of matrix profile. Yet, the concept is much older.

As stated above, I already extended STOMP to support k-NN profiles for collections (multivariate and unequal length compatible).

Great.

I think that X is not meaningful for motif discovery.

In the context of motif search in a single series I agree, but wouldn't there be some interest when dealing with a collection ? For example find motifs in the collection at the condition that they are similar to a subsequence in X ? (This is pure speculation)

I would not say that this is impossible, but I have not seen it. :)

[baraline]

Simplicity :) But I agree that you could have multiple series in fit, too - this would mimic the Shapelet use case, I suppose?

I'm not 100% sure what you mean, but in a sense yes ? For example with a brute force neighbour search, just compute the distance of the subsequence given in find_neighbors to all candidates subsequences in all series of the collection given in fit, and take the k best overall, (considering neighbouring matches/self matches if specified by parameters).

I see. I personally do not like to use the terms matrix-profile for simple k-NN distances or k-NN indices though. It was a brilliant re-framing of EK, such that all 1-NN algorithms are now suddenly an instance of matrix profile. Yet, the concept is much older.

I'm not against the idea of a different naming, especially if methods labelled differently from MPs would fit in the base class without much change of parameter/interface. Would you have any proposal? Something like BaseNeighborhoodSearch ?

[patrickzib]

I'm not against the idea of a different naming, especially if methods labelled differently from MPs would fit in the base class without much change of parameter/interface. Would you have any proposal? Something like BaseNeighborhoodSearch ?

In sklearn it is simply NearestNeighbors ? :) And it returns indices and distances.

https://scikit-learn.org/1.5/modules/neighbors.html

[review-notebook-app[bot]]

Check out this pull request on 

See visual diffs & provide feedback on Jupyter Notebooks.

---

Powered by ReviewNB

[baraline]

I'll leave the implementation of k-motiflets for later as a separate estimator so I can focus on getting the testing, tags and docs right for this PR to have the structure for the module set.

[baraline]

Based on your comment @MatthewMiddlehurst, I think another set of base class for neighbours / motifs estimator is necessary to not have weird thing in the series & collection base classes. I wanted to avoid creating too many bases classes, but it seems necessary to have "cleaner" ones. I'll put it in place and then you can check back if it feels better.

[baraline]

Tried to make additional base classes, but this made the whole module structure feel too overcomplicated. Reverted and instead factored some functions away from the base class and made a fit_predict for stomp to avoid the weird X=None possibility in predict. Open to suggestions if you have some

[MatthewMiddlehurst]

Its all experimental. Better to just get it in when clear issues are resolved then iterate.

[MatthewMiddlehurst]

It is also possible I am misunderstanding the goal a bit. If you want to do something that fits a collection and predicts on a series, we probably need a new base class for that. The collection and series bases are not really built for it. Not saying has to be done in this PR, but probably where we want to end up.

[baraline]

I think we need to explore this a bit further down the road when more estimators are added to see if it would really fit a use case. This could also be solved with a simple wrapper like predict_series calling self.predict([X]), but let's give it some thought first agree.

[baraline]

Agreed, will resume work on this module during summer when things cool down, and testing will definitly be an important part of the work