STUMPY is a powerful and scalable Python library for computing a Matrix Profile, which can be used for a variety of time series data mining tasks

Overview
PyPI Version PyPI Downloads Conda-forge Version Conda-forge Downloads License Test Status Code Coverage ReadTheDocs Status Binder JOSS DOI FOSSA Twitter

STUMPY Logo

STUMPY

STUMPY is a powerful and scalable library that efficiently computes something called the matrix profile, which can be used for a variety of time series data mining tasks such as:

  • pattern/motif (approximately repeated subsequences within a longer time series) discovery
  • anomaly/novelty (discord) discovery
  • shapelet discovery
  • semantic segmentation
  • streaming (on-line) data
  • fast approximate matrix profiles
  • time series chains (temporally ordered set of subsequence patterns)
  • and more ...

Whether you are an academic, data scientist, software developer, or time series enthusiast, STUMPY is straightforward to install and our goal is to allow you to get to your time series insights faster. See documentation for more information.

How to use STUMPY

Please see our API documentation for a complete list of available functions and see our informative tutorials for more comprehensive example use cases. Below, you will find code snippets that quickly demonstrate how to use STUMPY.

Typical usage (1-dimensional time series data) with STUMP:

import stumpy
import numpy as np

if __name__ == "__main__":
    your_time_series = np.random.rand(10000)
    window_size = 50  # Approximately, how many data points might be found in a pattern

    matrix_profile = stumpy.stump(your_time_series, m=window_size)

Distributed usage for 1-dimensional time series data with Dask Distributed via STUMPED:

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

if __name__ == "__main__":
    dask_client = Client()

    your_time_series = np.random.rand(10000)
    window_size = 50  # Approximately, how many data points might be found in a pattern

    matrix_profile = stumpy.stumped(dask_client, your_time_series, m=window_size)

GPU usage for 1-dimensional time series data with GPU-STUMP:

import stumpy
import numpy as np
from numba import cuda

if __name__ == "__main__":
    your_time_series = np.random.rand(10000)
    window_size = 50  # Approximately, how many data points might be found in a pattern
    all_gpu_devices = [device.id for device in cuda.list_devices()]  # Get a list of all available GPU devices

    matrix_profile = stumpy.gpu_stump(your_time_series, m=window_size, device_id=all_gpu_devices)

Multi-dimensional time series data with MSTUMP:

import stumpy
import numpy as np

if __name__ == "__main__":
    your_time_series = np.random.rand(3, 1000)  # Each row represents data from a different dimension while each column represents data from the same dimension
    window_size = 50  # Approximately, how many data points might be found in a pattern

    matrix_profile, matrix_profile_indices = stumpy.mstump(your_time_series, m=window_size)

Distributed multi-dimensional time series data analysis with Dask Distributed MSTUMPED:

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

if __name__ == "__main__":
    dask_client = Client()

    your_time_series = np.random.rand(3, 1000)   # Each row represents data from a different dimension while each column represents data from the same dimension
    window_size = 50  # Approximately, how many data points might be found in a pattern

    matrix_profile, matrix_profile_indices = stumpy.mstumped(dask_client, your_time_series, m=window_size)

Time Series Chains with Anchored Time Series Chains (ATSC):

import stumpy
import numpy as np

if __name__ == "__main__":
    your_time_series = np.random.rand(10000)
    window_size = 50  # Approximately, how many data points might be found in a pattern

    matrix_profile = stumpy.stump(your_time_series, m=window_size)

    left_matrix_profile_index = matrix_profile[:, 2]
    right_matrix_profile_index = matrix_profile[:, 3]
    idx = 10  # Subsequence index for which to retrieve the anchored time series chain for

    anchored_chain = stumpy.atsc(left_matrix_profile_index, right_matrix_profile_index, idx)

    all_chain_set, longest_unanchored_chain = stumpy.allc(left_matrix_profile_index, right_matrix_profile_index)

Semantic Segmentation with Fast Low-cost Unipotent Semantic Segmentation (FLUSS):

import stumpy
import numpy as np

if __name__ == "__main__":
    your_time_series = np.random.rand(10000)
    window_size = 50  # Approximately, how many data points might be found in a pattern

    matrix_profile = stumpy.stump(your_time_series, m=window_size)

    subseq_len = 50
    correct_arc_curve, regime_locations = stumpy.fluss(matrix_profile[:, 1],
                                                    L=subseq_len,
                                                    n_regimes=2,
                                                    excl_factor=1
                                                    )

Dependencies

Supported Python and NumPy versions are determined according to the NEP 29 deprecation policy.

Where to get it

Conda install (preferred):

conda install -c conda-forge stumpy

PyPI install, presuming you have numpy, scipy, and numba installed:

python -m pip install stumpy

To install stumpy from source, see the instructions in the documentation.

Documentation

In order to fully understand and appreciate the underlying algorithms and applications, it is imperative that you read the original publications. For a more detailed example of how to use STUMPY please consult the latest documentation or explore the following tutorials:

  1. The Matrix Profile
  2. STUMPY Basics
  3. Time Series Chains
  4. Semantic Segmentation

Performance

We tested the performance of computing the exact matrix profile using the Numba JIT compiled version of the code on randomly generated time series data with various lengths (i.e., np.random.rand(n)) along with different CPU and GPU hardware resources.

STUMPY Performance Plot

The raw results are displayed in the table below as Hours:Minutes:Seconds.Milliseconds and with a constant window size of m = 50. Note that these reported runtimes include the time that it takes to move the data from the host to all of the GPU device(s). You may need to scroll to the right side of the table in order to see all of the runtimes.

i n = 2i GPU-STOMP STUMP.2 STUMP.16 STUMPED.128 STUMPED.256 GPU-STUMP.1 GPU-STUMP.2 GPU-STUMP.DGX1 GPU-STUMP.DGX2
6 64 00:00:10.00 00:00:00.00 00:00:00.00 00:00:05.77 00:00:06.08 00:00:00.03 00:00:01.63 NaN NaN
7 128 00:00:10.00 00:00:00.00 00:00:00.00 00:00:05.93 00:00:07.29 00:00:00.04 00:00:01.66 NaN NaN
8 256 00:00:10.00 00:00:00.00 00:00:00.01 00:00:05.95 00:00:07.59 00:00:00.08 00:00:01.69 00:00:06.68 00:00:25.68
9 512 00:00:10.00 00:00:00.00 00:00:00.02 00:00:05.97 00:00:07.47 00:00:00.13 00:00:01.66 00:00:06.59 00:00:27.66
10 1024 00:00:10.00 00:00:00.02 00:00:00.04 00:00:05.69 00:00:07.64 00:00:00.24 00:00:01.72 00:00:06.70 00:00:30.49
11 2048 NaN 00:00:00.05 00:00:00.09 00:00:05.60 00:00:07.83 00:00:00.53 00:00:01.88 00:00:06.87 00:00:31.09
12 4096 NaN 00:00:00.22 00:00:00.19 00:00:06.26 00:00:07.90 00:00:01.04 00:00:02.19 00:00:06.91 00:00:33.93
13 8192 NaN 00:00:00.50 00:00:00.41 00:00:06.29 00:00:07.73 00:00:01.97 00:00:02.49 00:00:06.61 00:00:33.81
14 16384 NaN 00:00:01.79 00:00:00.99 00:00:06.24 00:00:08.18 00:00:03.69 00:00:03.29 00:00:07.36 00:00:35.23
15 32768 NaN 00:00:06.17 00:00:02.39 00:00:06.48 00:00:08.29 00:00:07.45 00:00:04.93 00:00:07.02 00:00:36.09
16 65536 NaN 00:00:22.94 00:00:06.42 00:00:07.33 00:00:09.01 00:00:14.89 00:00:08.12 00:00:08.10 00:00:36.54
17 131072 00:00:10.00 00:01:29.27 00:00:19.52 00:00:09.75 00:00:10.53 00:00:29.97 00:00:15.42 00:00:09.45 00:00:37.33
18 262144 00:00:18.00 00:05:56.50 00:01:08.44 00:00:33.38 00:00:24.07 00:00:59.62 00:00:27.41 00:00:13.18 00:00:39.30
19 524288 00:00:46.00 00:25:34.58 00:03:56.82 00:01:35.27 00:03:43.66 00:01:56.67 00:00:54.05 00:00:19.65 00:00:41.45
20 1048576 00:02:30.00 01:51:13.43 00:19:54.75 00:04:37.15 00:03:01.16 00:05:06.48 00:02:24.73 00:00:32.95 00:00:46.14
21 2097152 00:09:15.00 09:25:47.64 03:05:07.64 00:13:36.51 00:08:47.47 00:20:27.94 00:09:41.43 00:01:06.51 00:01:02.67
22 4194304 NaN 36:12:23.74 10:37:51.21 00:55:44.43 00:32:06.70 01:21:12.33 00:38:30.86 00:04:03.26 00:02:23.47
23 8388608 NaN 143:16:09.94 38:42:51.42 03:33:30.53 02:00:49.37 05:11:44.45 02:33:14.60 00:15:46.26 00:08:03.76
24 16777216 NaN NaN NaN 14:39:11.99 07:13:47.12 20:43:03.80 09:48:43.42 01:00:24.06 00:29:07.84
NaN 17729800 09:16:12.00 NaN NaN 15:31:31.75 07:18:42.54 23:09:22.43 10:54:08.64 01:07:35.39 00:32:51.55
25 33554432 NaN NaN NaN 56:03:46.81 26:27:41.29 83:29:21.06 39:17:43.82 03:59:32.79 01:54:56.52
26 67108864 NaN NaN NaN 211:17:37.60 106:40:17.17 328:58:04.68 157:18:30.50 15:42:15.94 07:18:52.91
NaN 100000000 291:07:12.00 NaN NaN NaN 234:51:35.39 NaN NaN 35:03:44.61 16:22:40.81
27 134217728 NaN NaN NaN NaN NaN NaN NaN 64:41:55.09 29:13:48.12

Hardware Resources

GPU-STOMP: These results are reproduced from the original Matrix Profile II paper - NVIDIA Tesla K80 (contains 2 GPUs) and serves as the performance benchmark to compare against.

STUMP.2: stumpy.stump executed with 2 CPUs in Total - 2x Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz processors parallelized with Numba on a single server without Dask.

STUMP.16: stumpy.stump executed with 16 CPUs in Total - 16x Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz processors parallelized with Numba on a single server without Dask.

STUMPED.128: stumpy.stumped executed with 128 CPUs in Total - 8x Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz processors x 16 servers, parallelized with Numba, and distributed with Dask Distributed.

STUMPED.256: stumpy.stumped executed with 256 CPUs in Total - 8x Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz processors x 32 servers, parallelized with Numba, and distributed with Dask Distributed.

GPU-STUMP.1: stumpy.gpu_stump executed with 1x NVIDIA GeForce GTX 1080 Ti GPU, 512 threads per block, 200W power limit, compiled to CUDA with Numba, and parallelized with Python multiprocessing

GPU-STUMP.2: stumpy.gpu_stump executed with 2x NVIDIA GeForce GTX 1080 Ti GPU, 512 threads per block, 200W power limit, compiled to CUDA with Numba, and parallelized with Python multiprocessing

GPU-STUMP.DGX1: stumpy.gpu_stump executed with 8x NVIDIA Tesla V100, 512 threads per block, compiled to CUDA with Numba, and parallelized with Python multiprocessing

GPU-STUMP.DGX2: stumpy.gpu_stump executed with 16x NVIDIA Tesla V100, 512 threads per block, compiled to CUDA with Numba, and parallelized with Python multiprocessing

Running Tests

Tests are written in the tests directory and processed using PyTest and requires coverage.py for code coverage analysis. Tests can be executed with:

./test.sh

Python Version

STUMPY supports Python 3.7+ and, due to the use of unicode variable names/identifiers, is not compatible with Python 2.x. Given the small dependencies, STUMPY may work on older versions of Python but this is beyond the scope of our support and we strongly recommend that you upgrade to the most recent version of Python.

Getting Help

First, please check the discussions and issues on Github to see if your question has already been answered there. If no solution is available there feel free to open a new discussion or issue and the authors will attempt to respond in a reasonably timely fashion.

Contributing

We welcome contributions in any form! Assistance with documentation, particularly expanding tutorials, is always welcome. To contribute please fork the project, make your changes, and submit a pull request. We will do our best to work through any issues with you and get your code merged into the main branch.

Citing

If you have used this codebase in a scientific publication and wish to cite it, please use the Journal of Open Source Software article.

S.M. Law, (2019). STUMPY: A Powerful and Scalable Python Library for Time Series Data Mining. Journal of Open Source Software, 4(39), 1504.
@article{law2019stumpy,
  title={{STUMPY: A Powerful and Scalable Python Library for Time Series Data Mining}},
  author={Law, Sean M.},
  journal={{The Journal of Open Source Software}},
  volume={4},
  number={39},
  pages={1504},
  year={2019}
}

References

Yeh, Chin-Chia Michael, et al. (2016) Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View that Includes Motifs, Discords, and Shapelets. ICDM:1317-1322. Link

Zhu, Yan, et al. (2016) Matrix Profile II: Exploiting a Novel Algorithm and GPUs to Break the One Hundred Million Barrier for Time Series Motifs and Joins. ICDM:739-748. Link

Yeh, Chin-Chia Michael, et al. (2017) Matrix Profile VI: Meaningful Multidimensional Motif Discovery. ICDM:565-574. Link

Zhu, Yan, et al. (2017) Matrix Profile VII: Time Series Chains: A New Primitive for Time Series Data Mining. ICDM:695-704. Link

Gharghabi, Shaghayegh, et al. (2017) Matrix Profile VIII: Domain Agnostic Online Semantic Segmentation at Superhuman Performance Levels. ICDM:117-126. Link

Zhu, Yan, et al. (2017) Exploiting a Novel Algorithm and GPUs to Break the Ten Quadrillion Pairwise Comparisons Barrier for Time Series Motifs and Joins. KAIS:203-236. Link

Zhu, Yan, et al. (2018) Matrix Profile XI: SCRIMP++: Time Series Motif Discovery at Interactive Speeds. ICDM:837-846. Link

Yeh, Chin-Chia Michael, et al. (2018) Time Series Joins, Motifs, Discords and Shapelets: a Unifying View that Exploits the Matrix Profile. Data Min Knowl Disc:83-123. Link

Gharghabi, Shaghayegh, et al. (2018) "Matrix Profile XII: MPdist: A Novel Time Series Distance Measure to Allow Data Mining in More Challenging Scenarios." ICDM:965-970. Link

Zimmerman, Zachary, et al. (2019) Matrix Profile XIV: Scaling Time Series Motif Discovery with GPUs to Break a Quintillion Pairwise Comparisons a Day and Beyond. SoCC '19:74-86. Link

Akbarinia, Reza, and Betrand Cloez. (2019) Efficient Matrix Profile Computation Using Different Distance Functions. arXiv:1901.05708. Link

Kamgar, Kaveh, et al. (2019) Matrix Profile XV: Exploiting Time Series Consensus Motifs to Find Structure in Time Series Sets. ICDM:1156-1161. Link

License & Trademark

STUMPY
Copyright 2019 TD Ameritrade. Released under the terms of the 3-Clause BSD license.
STUMPY is a trademark of TD Ameritrade IP Company, Inc. All rights reserved.
Issues
  • Added Annotation Vectors Tutorial, #177

    Added Annotation Vectors Tutorial, #177

    Added first draft of the Annotation Vectors Tutorial, requested in issue #177, for feedback. The tutorial includes all 4 examples explored in the Matrix Profile V paper (https://www.cs.ucr.edu/~hdau001/guided_motif_search/). Planning to remove 2/3 out of the 4 examples. Let me know which ones I should keep/remove.

    Pull Request Checklist

    Below is a simple checklist but please do not hesitate to ask for assistance!

    • [x] Fork, clone, and checkout the newest version of the code
    • [x] Create a new branch
    • [x] Make necessary code changes
    • [x] Install black (i.e., python -m pip install black or conda install -c conda-forge black)
    • [x] Install flake8 (i.e., python -m pip install flake8 or conda install -c conda-forge flake8)
    • [x] Install pytest-cov (i.e., python -m pip install pytest-cov or conda install -c conda-forge pytest-cov)
    • [x] Run black . in the root stumpy directory
    • [x] Run flake8 . in the root stumpy directory
    • [x] Run ./setup.sh && ./test.sh in the root stumpy directory
    • [x] Reference a Github issue (and create one if one doesn't already exist)
    opened by alvii147 88
  • [WIP] Module for motif and discord discovery

    [WIP] Module for motif and discord discovery

    I gave the motif discovery module a go (issue #184), what do you think? (Ignore all changes outside motifs.py and test_motifs.py, as we discuss this in another PR)

    There are still more tests to be done, but I'm not sure how to approach it yet. Ideally I'd like a naive_k_motifs method.

    opened by mexxexx 81
  • Add Matrix Profile Subspace For MSTUMP/MSTUMPED

    Add Matrix Profile Subspace For MSTUMP/MSTUMPED

    Following Definition 13 in the mSTAMP paper we can return a "matrix profile subspace"

    enhancement help wanted 
    opened by seanlaw 62
  • Consensus Motifs: Ostinato algorithm; most central motif; reproduce Fig 1, 2, 9 from paper Matrix Profile XV

    Consensus Motifs: Ostinato algorithm; most central motif; reproduce Fig 1, 2, 9 from paper Matrix Profile XV

    This uses the mtDNA example. Ostinato transcribed from table 2 in paper. Performance is really slow.

    resolves #277, resolves #278

    Pull Request Checklist

    Below is a simple checklist but please do not hesitate to ask for assistance!

    • [x] Fork, clone, and checkout the newest version of the code
    • [x] Create a new branch
    • [x] Make necessary code changes
    • [x] Install black (i.e., python -m pip install black or conda install black)
    • [x] Install flake8 (i.e., python -m pip install flake8 or conda install flake8)
    • [x] Install pytest-cov (i.e., python -m pip install pytest-cov or conda install pytest-cov)
    • [x] Run black . in the root stumpy directory
    • [x] Run flake8 . in the root stumpy directory
    • [x] Run ./setup.sh && ./test.sh in the root stumpy directory
    • [x] Reference a Github issue (and create one if one doesn't already exist)
    opened by DanBenHa 58
  • Add the introduction part to Snippet Tutorial

    Add the introduction part to Snippet Tutorial

    Corresponding to Issue #374

    Pull Request Checklist

    Below is a simple checklist but please do not hesitate to ask for assistance!

    • [x] Fork, clone, and checkout the newest version of the code
    • [x] Create a new branch
    • [x] Make necessary code changes
    • [x] Install black (i.e., python -m pip install black or conda install -c conda-forge black)
    • [x] Install flake8 (i.e., python -m pip install flake8 or conda install -c conda-forge flake8)
    • [x] Install pytest-cov (i.e., python -m pip install pytest-cov or conda install -c conda-forge pytest-cov)
    • [x] Run black . in the root stumpy directory
    • [x] Run flake8 . in the root stumpy directory
    • [ ] Run ./setup.sh && ./test.sh in the root stumpy directory
    • [x] Reference a Github issue (and create one if one doesn't already exist)
    opened by Ninimama 47
  • [WIP] Add finite tracking dictionary

    [WIP] Add finite tracking dictionary

    Work in Progress for Issue #206

    Really clean codebase, Sean. Just updating as I work so you know there's progress. Created finite mask attribute that tracks with _T.

    TODO: Find where to apply finite mask TODO: Add test to include nan/inf data

    Pull Request Checklist

    • [x] Fork, clone, and checkout the newest version of the code
    • [x] Make necessary changes
    • [x] Install black (i.e., python -m pip install black or conda install black)
    • [x] Install flake8 (i.e., python -m pip install flake8 or conda install flake8)
    • [x] Install pytest-cov (i.e., python -m pip install pytest-cov or conda install pytest-cov)
    • [x] Run black . in the root stumpy directory
    • [x] Run flake8 . in the root stumpy directory
    • [x] Run ./setup.py && ./test.sh in the root stumpy directory
    • [x] Reference a Github issue (and create one if one doesn't already exist)
    opened by JosephTLucas 35
  • Fixed Issue #115

    Fixed Issue #115

    This pull request fixes issue #115.

    The fix itself is simple. We set the mean value of every sub sequence that contains at least one inf/NaN value to infinity. Afterwards, we replace the values in the sequences with 0 so to not get any computational problems. The marked sub sequences are then considered at two points: When calculating the distance profile of Q with T, we have to set the distance from Q to every illegal sequence in T to infinity, and if Q itself is an illegal sequence, the whole distance profile needs to be set to infinity.

    opened by mexxexx 34
  • Add `aampi`

    Add `aampi`

    This should be fairly straightforward in theory using convolution.

    We also need to add this to the API documentation

    enhancement 
    opened by seanlaw 31
  • Speed Up GPU-STUMP

    Speed Up GPU-STUMP

    Currently, the code works with CuPy but isn't performant. This issue is to explore the improvement of the performance.

    enhancement 
    opened by seanlaw 30
  • Fixed Issue #115

    Fixed Issue #115

    This pull request fixes Issue #115, the handling of NaN and inf values in the 1D Matrix Profile Algorithms.

    opened by mexxexx 29
  • Add DTW Motif Discovery - SWAMP

    Add DTW Motif Discovery - SWAMP

    The SWAMP paper can be found here

    The supplementary webpage is here

    The code is here

    The data is here

    enhancement help wanted notebook reproducer 
    opened by seanlaw 0
  • Add Contrast Profile Tutorial

    Add Contrast Profile Tutorial

    This paper is here

    The supporting site is here

    The main goal of a contrast profile is to annotate each subsequence of a time series so that you can discover if there are "good" subsequences that can be used for time series classification (see Definition 6 in the paper above). In order to extract these subsequences, you need to have 2 time series. One time series, , and another time series, . It is recommended that you compute the the Contrast Profile only when you believe that the two following assumptions are likely to be true:

    • contains at least two behaviors that are unique to the phenomena of interest.
    • contains zero behaviors of interest.
    help wanted notebook reproducer 
    opened by seanlaw 0
  • [WIP] Added stump_tiles module (#248)

    [WIP] Added stump_tiles module (#248)

    This is a work-in-progress pull request addressing issue #248, i.e. implementation of a method that reduces cache misses while computing the Matrix Profile using stump.

    How it works right now

    Let us first briefly explore how stump works right now and what's wrong with it.

    Consider a time series of length 20 and a window of 6. Then we know the distance matrix will be a 15 x 15 matrix (20 - 6 + 1 = 15). Furthermore, the exclusion zone will be ±2 (np.ceil(6 / 4) = 2). Thus the distance matrix will look something like this:

    Empty Distance Matrix

    The grey area is the exclusion zone.

    Currently, if this time series and window are passed into stump, each of the diagonals in the matrix will be processed one by one:

    stump Matrix

    The traversal will be along the yellow dividers.

    The benefit with this method is the benefit we get from computing by diagonals. Computing each distance is a lot simpler given the distance from the previous index in the diagonal. For eg, once we compute the distance for point (3, 0), we can use it to calculate the distance for point (4, 1).

    The issue with this is, the cache is more likely to store points that are closer to each other, and so traversing an entire diagonal is likely to cause too many cache misses.

    How we want it to work

    While traversing diagonally is certainly the right approach, traversing entire diagonals will negatively affect performance. Instead, we want to split the matrix into smaller tiles, each of which will be divides into groups of diagonals.

    Suppose the tile size is set to 4 and the number of diagonals to be iterated together is set to 2. Then, the distance matrix will be divided like this:

    Tiles Matrix

    The matrix is split into 4 x 4 tiles (except near the edges). Tiles with blue borders indicate that there are distances to traverse within those tiles, tiles with red borders indicate that we should skip those tiles as there are no distances to traverse within them. Further more, each of the diagonals within the blue tiles are split into groups of 2 (or less). Each diagonal groups are traversed together.

    For example, if we were to traverse the tile colored light pink, we would do so in the following order:

    (8, 4)
    (8, 5)
    (9, 5)
    (9, 6)
    (10, 6)
    (10, 7)
    (11, 7)
    (9, 4)
    (10, 4)
    (10, 5)
    (11, 5)
    (11, 6)
    (11, 4)
    

    What's done so far

    The changes in the alvii147/cache_optimization branch is the first step to accomplishing this.

    Two new functions were added to core.py, _get_tiles and _get_tiles_ranges, and a new module was added named stump_tiles.py.

    core._get_tiles

    _get_tiles(m, n_A, n_B, diags, tile_size)
    
    Parameters
    ----------
    m : int
        Window size
    
    n_A : ndarray
        The length of time series `T_A`
    
    n_B : ndarray
        The length of time series `T_B`
    
    diags : ndarray
        The diagonal indices of interest
    
    tile_size : int
        Maximum length of each tile
    

    _get_tiles can be used to split the distance matrix into tiles of a given size. It returns tiles, an array of 2-column arrays, with each element representing each tile. The contents of each 2-column array are described below.

    2-column array contents:
    
    [ y_offset                x_offset            ]
    [tile_height              tile_width          ]
    [lower_diagonal_index     upper_diagonal_index]
    [tile_weight              tile_validity       ]
    
    x_offset, y_offset: position of the tile with respect to the distance matrix
    tile_height, tile_width: dimensions of the tile
    lower_diagonal_index, upper_diagonal_index: range of diagonals to be traversed within the tile
    tile_weight: number of distances to be computed within the tile
    tile_validity: 0 if no distances within tile are to be computed, 1 otherwise
    

    The first 4 tiles of the distance matrix considered above should return the following result:

    [[ 0  0]
     [ 4  4]
     [ 3  4]
     [ 1  1]]
    
    [[ 0  4]
     [ 4  4]
     [-1  4]
     [13  1]]
    
    [[ 0  8]
     [ 4  4]
     [-3  4]
     [16  1]]
    
    [[ 0 12]
     [ 4  3]
     [-3  2]
     [12  1]]
    
    ...
    

    core._get_tiles_ranges

    _get_tiles_ranges(tiles, n_threads)
    
    Split given `tiles` into `n_threads`.
    
    Parameters
    ----------
    tiles : ndarray
        An array of two column arrays representing each tile
    
    n_threads : int
        Number of threads to split the tiles into
    
    Returns
    -------
    tiles_ranges : ndarray
        A two-dimensional array representing tile indices for each thread
    

    _get_tiles_ranges can be used to split the tiles that we obtain from _get_tiles into n_threads given threads. This is done by sorting the tiles in descending order of tile_weight, then assigning them one by one to each thread. Once we reach the end of the thread, we keep assigning the tiles to the threads in reverse order.

    For example, suppose we have tiles of weights in descending order [7, 6, 5, 3, 2, 1] and we have 3 threads to divide these into. We start by assigning 7, 6, and 5 to the first three threads respectively. Then the third thread gets 3, second thread gets 2, and first thread gets 1. So the division between the threads would look something like this:

    First thread: [7 1]
    Second thread: [6 2]
    Third thread: [5 3]
    

    This way, the workload is most equally divided.

    If we were to run _get_tiles on the previously described example, and then divide those tiles into 3 threads using _get_tiles_ranges, we would obtain the following array, where each row are the indices of the tiles assigned to each thread:

    [[ 2, 11, 10, 13, 12, -1]
     [ 6,  3,  5, 14,  9, -1]
     [ 1,  7,  0, 15,  8,  4]]
    

    NOTE: -1 is just a blank slot.

    stump_tiles

    The stump_tiles module is a modified version of stump. While stump calls _stump which calls _compute_diagonal, stump_tiles calls _stump_tiles, which calls _compute_tiles.

    _stump_tiles will call core._get_tiles and core._get_tiles_ranges to get tiles data and pass each group of tiles to _compute_tiles in a single thread. _compute_tiles will process the given tiles and divide each tile into "chunks" of tiles that are to be processed together.

    The default tile size, STUMPY_TILE_SIZE and the default number of diagonal to traverse together, STUMPY_DIAGONALS_CHUNK_SIZE are current defined in config.py.

    ...
    STUMPY_TILE_SIZE = 1000
    STUMPY_DIAGONALS_CHUNK_SIZE = 100
    
    

    Testing

    The only testing module added so far is test_stump_tiles.py, which is copied over and modified from test_stump.py. Use the following command to run them:

    export NUMBA_DISABLE_JIT=1
    export NUMBA_ENABLE_CUDASIM=1
    py.test -x -W ignore::RuntimeWarning -W ignore::DeprecationWarning tests/test_stump_tiles.py
    
    unset NUMBA_DISABLE_JIT
    unset NUMBA_ENABLE_CUDASIM
    py.test -x -W ignore::RuntimeWarning -W ignore::DeprecationWarning tests/test_stump_tiles.py
    

    All test cases in test_stump_tiles are currently PASSING.

    Performance

    Currently stump_tiles performs very poorly on relatively smaller time series, and marginally faster on relatively larger ones. Outlined below are the performances comparisons stump and stump_tiles for different time series lengths.

    Time Series Length | Window Size m | stump Performance (seconds) | stump_tiles Performance (seconds) | Percentage Improvement --- | --- | --- | --- | --- 1000 | 10 | 0.016 | 0.016 | 0.0% 2500 | 10 | 0.016 | 0.031 | -100.0% 5000 | 10 | 0.06 | 0.078 | -30.77% 10000 | 10 | 0.269 | 0.219 | 18.61% 25000 | 10 | 1.533 | 1.366 | 10.91% 50000 | 10 | 6.262 | 5.206 | 16.87% 100000 | 10 | 25.189 | 20.589 | 18.27% 200000 | 10 | 104.818 | 84.124 | 19.74% 250000 | 10 | 164.197 | 130.789 | 20.35%

    You may use the following script for testing performance:

    import stumpy
    import numpy as np
    import numpy.testing as npt
    import time
    
    def performance_test(m, ts_len):
        ts = np.random.rand(ts_len)
    
        print('\nTime series length:', ts_len)
        print('Window length:', m)
    
        time_elapsed = time.time()
        stump_mp = stumpy.stump(ts, m=m)
        time_elapsed = time.time() - time_elapsed
        print('stump performance (seconds):', time_elapsed)
    
        time_elapsed = time.time()
        stump_tiles_mp = stumpy.stump_tiles(ts, m=m)
        time_elapsed = time.time() - time_elapsed
        print('stump_tiles performance (seconds):', time_elapsed)
    
        npt.assert_almost_equal(stump_tiles_mp, stump_mp)
    
    if __name__ == "__main__":
        stumpy.stump(np.random.rand(1000), m=200)
        stumpy.stump_tiles(np.random.rand(1000), m=200)
    
        parameters = (
            (10, 1000),
            (10, 2500),
            (10, 5000),
            (100, 10000),
            (100, 100000),
            (100, 200000),
            (100, 250000),
        )
        for param in parameters:
            performance_test(*param)
    

    Note that the performance may vary with the values of STUMPY_TILE_SIZE and STUMPY_DIAGONALS_CHUNK_SIZE, as well as with different systems.

    Okay, but what now?

    There's still a lot to do, here are a few things that come to mind.

    Time different components

    Use the time module to time different functions that we call, namely _get_tiles, _get_tiles_ranges and _compute_tiles, find out where exactly we lose time. If any of the components take time that is exponentially increasing with the number of distances, that's a good place for possible optimization.

    Optimize _get_tiles_ranges

    I am almost certain _get_tiles_ranges can be simplified. Currently this function sorts the tiles by weight, which is very expensive and may not be worth it. One thing to remember, the results of _get_tiles_ranges need not be perfect, the tiles don't need to be perfectly equally split among the threads. There's no point in dividing it perfectly if we spend a lot of time doing it. A roughly equal division is also good enough if it saves time.

    Optimize _compute_tiles

    I will also not be surprised if _compute_tiles isn't perfectly optimized. There may be room for improvement with the way the iterations are done.

    Find good values for STUMPY_TILE_SIZE and STUMPY_DIAGONALS_CHUNK_SIZE

    This is a tough one, since it's system dependent. Section 4.2.2 of the Time Series Analysis with Matrix Profile on HPC Systems Paper may help with this.

    Make the code NumPy and Numba friendly

    Some places may use native Python functions, such as range. These should be replaced with NumPy equivalents, such as np.arange.

    opened by alvii147 13
  • Add GPU Sliding Dot Product (FFT Convolution)

    Add GPU Sliding Dot Product (FFT Convolution)

    Currently, we have a NumPy/SciPy-based function that computes a sliding dot product between two 1D arrays, Q and T, by performing a (FFT) convolution:

    from scipy.signal import convolve
    
    def sliding_dot_product(Q, T):
        n = T.shape[0]
        m = Q.shape[0]
        Qr = np.flipud(Q)  # Reverse/flip Q
        QT = convolve(Qr, T)
    
        return QT.real[m - 1 : n]
    

    When Q and/or T are large it would be great to give users the ability to move the QT = convolve(Qr, T) line onto the GPU but without adding any new dependencies (currently, we only have numpy, scipy, and numba as dependencies and we'd like to keep it that way). When we explored this a few years ago (albeit in 2017), the options were to use pyculib OR cupy but both seemed like overkill (from the standpoint of adding another dependency) given that we only needed a single function.

    Another thing to consider is what (if any) cuda libraries need to be installed by the user in order to access cuFFT. Currently, when a user tries to access GPU-based Numba code, it is assumed that:

    1. They have an appropriate NVIDIA GPU
    2. They have installed the correct drivers
    3. They have installed the correct cudatoolkit>=10

    Is there anything else that is needed?

    enhancement help wanted 
    opened by seanlaw 3
  • Add Reticulate Tutorial - `stumpyr`

    Add Reticulate Tutorial - `stumpyr`

    Occasionally, users have asked if there was a way to use STUMPY in the R statistical software. It would be nice to have a simple tutorial that explained how to leverage the Reticulate package

    help wanted documentation enhancement 
    opened by seanlaw 6
  • Add `normalize` Parameter to `stumpy.stimp`

    Add `normalize` Parameter to `stumpy.stimp`

    Currently, the stumpy.stimp function (as well as stumpy.stimped and stumpy.gpu_stimp) only work with z-normalized matrix profiles. The "pan matrix profile" is generated by computing matrix profiles with different subsequence window sizes and then each individual matrix profile is then normalized by their corresponding subsequence length according to:

    m = 25
    norm = 1.0 / np.sqrt(2 * m)
    mp = mp * norm
    

    However, if the subsequence is not z-normalized first then this equation does not apply and we need to derive a different relationship for length normalizing the matrix profiles. Alternatively, one may simply normalize each matrix profile by the maximum value (i.e., np.max(mp)).

    enhancement 
    opened by seanlaw 0
  • [WIP] Add tutorial for MPdist

    [WIP] Add tutorial for MPdist

    This completes #290

    Just noticed that I incorrectly capitalized d in MPdist so I need to correct that. Another thing is to decide whether to include a hierarchical clustering for euclidean distance. I was not able to replicate the figure from the paper so far. I am finalizing a notebook currently which showcases multiple attempts to replicate the figure and will post it in Issues.

    Pull Request Checklist

    • [x] Fork, clone, and checkout the newest version of the code
    • [x] Create a new branch
    • [x] Make necessary code changes
    • [x] Install black (i.e., python -m pip install black or conda install -c conda-forge black)
    • [x] Install flake8 (i.e., python -m pip install flake8 or conda install -c conda-forge flake8)
    • [x] Install pytest-cov (i.e., python -m pip install pytest-cov or conda install -c conda-forge pytest-cov)
    • [x] Run black . in the root stumpy directory
    • [x] Run flake8 . in the root stumpy directory
    • [ ] Run ./setup.sh && ./test.sh in the root stumpy directory
    • [x] Reference a Github issue (and create one if one doesn't already exist)

    Skipped ./test.shbecause this is a documentation only pull request

    opened by asifmallik 10
  • Missing instruction on building and contributing to documentation

    Missing instruction on building and contributing to documentation

    Ideally, README.md should have a line or two under the documentation section on how to build the documentation.

    documentation enhancement 
    opened by asifmallik 3
  • [WIP] Add Tutorial for Matrix Profile XXI: MERLIN algorithm #Issue 417

    [WIP] Add Tutorial for Matrix Profile XXI: MERLIN algorithm #Issue 417

    Pull Request Checklist

    Below is a simple checklist but please do not hesitate to ask for assistance!

    • [x] Fork, clone, and checkout the newest version of the code
    • [x] Create a new branch
    • [x] Make necessary code changes
    • [x] Install black (i.e., python -m pip install black or conda install -c conda-forge black)
    • [x] Install flake8 (i.e., python -m pip install flake8 or conda install -c conda-forge flake8)
    • [x] Install pytest-cov (i.e., python -m pip install pytest-cov or conda install -c conda-forge pytest-cov)
    • [x] Run black . in the root stumpy directory
    • [x] Run flake8 . in the root stumpy directory
    • [x] Run ./setup.sh && ./test.sh in the root stumpy directory
    • [x] Reference a Github issue (and create one if one doesn't already exist)
    opened by Ninimama 23
  • Add Matrix Profile XXI MERLIN Algorithm for Anomaly Detection

    Add Matrix Profile XXI MERLIN Algorithm for Anomaly Detection

    Discussed in https://github.com/TDAmeritrade/stumpy/discussions/415

    Originally posted by udf2457 June 19, 2021 I was reading about MERLIN which was presented at ICDM 2020:

    • Matrix Profile XXI: MERLIN: Parameter-Free Discovery of Arbitrary Length Anomalies in Massive Time Series Archives. Takaaki Nakamura, Makoto Imamura, Ryan Mercer and Eamonn Keogh. ICDM 2020 [pdf,author's Matlab reference implementation]

    It would be really neat to see MERLIN implemented in stumpy

    enhancement 
    opened by seanlaw 13
Releases(v1.9.2)
Owner
TD Ameritrade
Open source by TD Ameritrade
TD Ameritrade
Evidently helps analyze machine learning models during validation or production monitoring

Evidently helps analyze machine learning models during validation or production monitoring. The tool generates interactive visual reports and JSON profiles from pandas DataFrame or csv files. Currently 6 reports are available.

Evidently AI 1.5k Oct 15, 2021
Merlion: A Machine Learning Framework for Time Series Intelligence

Merlion is a Python library for time series intelligence. It provides an end-to-end machine learning framework that includes loading and transforming data, building and training models, post-processing model outputs, and evaluating model performance. I

Salesforce 2k Oct 23, 2021
A data preprocessing package for time series data. Design for machine learning and deep learning.

A data preprocessing package for time series data. Design for machine learning and deep learning.

Allen Chiang 94 Sep 14, 2021
ThunderSVM: A Fast SVM Library on GPUs and CPUs

What's new We have recently released ThunderGBM, a fast GBDT and Random Forest library on GPUs. add scikit-learn interface, see here Overview The miss

Xtra Computing Group 1.3k Oct 14, 2021
Anomaly Detection and Correlation library

luminol Overview Luminol is a light weight python library for time series data analysis. The two major functionalities it supports are anomaly detecti

LinkedIn 969 Oct 12, 2021
A Python package for time series classification

pyts: a Python package for time series classification pyts is a Python package for time series classification. It aims to make time series classificat

Johann Faouzi 1.1k Oct 24, 2021
A python library for easy manipulation and forecasting of time series.

Time Series Made Easy in Python darts is a python library for easy manipulation and forecasting of time series. It contains a variety of models, from

Unit8 3k Oct 22, 2021
A unified framework for machine learning with time series

Welcome to sktime A unified framework for machine learning with time series We provide specialized time series algorithms and scikit-learn compatible

The Alan Turing Institute 4.6k Oct 15, 2021
A machine learning toolkit dedicated to time-series data

tslearn The machine learning toolkit for time series analysis in Python Section Description Installation Installing the dependencies and tslearn Getti

null 1.8k Oct 24, 2021
A machine learning toolkit dedicated to time-series data

tslearn The machine learning toolkit for time series analysis in Python Section Description Installation Installing the dependencies and tslearn Getti

null 1.8k Oct 17, 2021
Automated modeling and machine learning framework FEDOT

This repository contains FEDOT - an open-source framework for automated modeling and machine learning (AutoML). It can build custom modeling pipelines for different real-world processes in an automated way using an evolutionary approach. FEDOT supports classification (binary and multiclass), regression, clustering, and time series prediction tasks.

National Center for Cognitive Research of ITMO University 148 Jul 5, 2021
An open-source library of algorithms to analyse time series in GPU and CPU.

An open-source library of algorithms to analyse time series in GPU and CPU.

Shapelets 191 Oct 7, 2021
Nixtla is an open-source time series forecasting library.

Nixtla Nixtla is an open-source time series forecasting library. We are helping data scientists and developers to have access to open source state-of-

Nixtla 40 Oct 22, 2021
Data Efficient Decision Making

Data Efficient Decision Making

Microsoft 46 Oct 19, 2021
Microsoft contributing libraries, tools, recipes, sample codes and workshop contents for machine learning & deep learning.

Microsoft contributing libraries, tools, recipes, sample codes and workshop contents for machine learning & deep learning.

Microsoft 227 Oct 17, 2021
Visualize classified time series data with interactive Sankey plots in Google Earth Engine

sankee Visualize changes in classified time series data with interactive Sankey plots in Google Earth Engine Contents Description Installation Using P

Aaron Zuspan 47 Oct 5, 2021
MaD GUI is a basis for graphical annotation and computational analysis of time series data.

MaD GUI Machine Learning and Data Analytics Graphical User Interface MaD GUI is a basis for graphical annotation and computational analysis of time se

Machine Learning and Data Analytics Lab FAU 2 Oct 15, 2021
Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs (CIKM 2020)

Karate Club is an unsupervised machine learning extension library for NetworkX. Please look at the Documentation, relevant Paper, Promo Video, and Ext

Benedek Rozemberczki 1.4k Oct 14, 2021
Probabilistic time series modeling in Python

GluonTS - Probabilistic Time Series Modeling in Python GluonTS is a Python toolkit for probabilistic time series modeling, built around Apache MXNet (

Amazon Web Services - Labs 2.2k Oct 22, 2021