tsdistances

Introduction

tsdistances is a Python library (with Rust backend) for computing various pairwise distances between sets of time series data.

It provides efficient implementation of elastic distance measures such as Dynamic Time Warping (DTW), Longest Common Subsequence (LCSS), Time Warping Edit (TWE), and many others.

The library is designed to be fast and scalable, leveraging parallel computation and GPU support via Vulkan for improved performance.

Features

1. Multiple Distance Measures: Supports a wide range of time series distance measures:

   • Euclidean

   • CATCH22 Euclidean

   • Edit Distance with Real Penalty (ERP) optionally with GPU support

   • Longest Common Subsequence (LCSS) optionally with GPU support

   • Dynamic Time Warping (DTW) optionally with GPU support

   • Derivative Dynamic Time Warping (DDTW) optionally with GPU support

   • Weighted Dynamic Time Warping (WDTW) optionally with GPU support

   • Weighted Derivative Dynamic Time Warping (WDDTW) optionally with GPU support

   • Amerced Dynamic Time Warping (ADTW) optionally with GPU support

   • Move-Split-Merge (MSM) optionally with GPU support

   • Time Warp Edit Distance (TWE) optionally with GPU support

   • Shape-Based Distance (SBD)

   • MPDist

2. Parallel Computation: Utilizes multiple CPU cores to speed up computations.

3. GPU Acceleration: Optional GPU support based on Vulkan for even faster computations with Rust-GPU.

Benchmark

To evaluate the performance of our time series distance computation library, we conducted a comparative analysis with existing libraries.

We selected AEON as the primary competitor due to its comprehensive implementation of distance metrics, making it the most suitable for direct comparison. Several other libraries were considered, and while we did not conduct a full benchmark on all datasets, we reported their execution times on a subset of the UCR Archive datasets.

Computation times (in seconds) of our method across 23 datasets, comparing single-threaded, parallelized, and GPU implementations.

Installation

PIP

If you use pip, you can install tsdistances with:

    $ pip install tsdistances

From Source

This can be done by going through the following steps in sequence:

1. Install the latest Rust compiler
2. Install maturin: pip install maturin
3. Build the library:

   maturin develop --release
   

GPU Support

To build with GPU acceleration:

1. Install LunarG Vulkan SDK
2. Either:
   • Install SPIRV-Tools, or
   • Use pre-compiled tools with --features use-compiled-tools

maturin develop --release --features use-compiled-tools

Feature Flags

The library uses Cargo feature flags to control what gets compiled:

For Python development (default):

maturin develop --release
# or explicitly:
cargo build --release --features python,use-compiled-tools

For MATLAB bindings only (no Python dependency):

cargo build --release --no-default-features --features matlab

See matlab/README.md for detailed MATLAB installation instructions.

Usage

Example 1: Compute DTW Distance on CPU and GPU

        
    import numpy as np
    import tsdistances

    # Generate two random time series (1-D arrays of length 100)
    np.random.seed(0)
    x1 = np.random.rand(100)
    x2 = np.random.rand(100)

    # Compute DTW distance on CPU
    cpu_distance = tsdistances.dtw_distance(x1, x2, device='cpu')
    print(f"DTW distance (CPU): {cpu_distance}")

    gpu_distance = tsdistances.dtw_distance(x1, x2, device='gpu')

    print(f"DTW distance (GPU): {gpu_distance}")

Example 2: Pairwise Distances with Multiple Time Series and Parallel Computation

    import numpy as np
    import tsdistances

    # Generate a batch of 10 random time series (each of length 50)
    np.random.seed(42)
    X = np.random.rand(10, 50)

    # Pairwise DTW distances within the set X (on CPU, single thread)
    pairwise_distances = tsdistances.dtw_distance(X, par=False, device='cpu')
    print("Pairwise DTW distance matrix (CPU, single thread):")
    print(pairwise_distances)

    # Compare two batches: compute distances between each element of X and each element of Y
    Y = np.random.rand(8, 50)
    batch_distances = tsdistances.dtw_distance(X, Y, par=True, device='cpu')
    print("Batch DTW distance matrix (X vs Y):")
    print(batch_distances)

Notes

1. device='gpu' enables GPU acceleration.

2. par controls parallelism. Set it to True to use all available CPU cores.

3. If v is not provided, the function computes pairwise distances within u.

Important: Results will differ between CPU and GPU due to floating-point precision:

CPU computations use f64 (double precision) for higher numerical accuracy.

GPU computations use f32 (single precision) for better performance.
For instance, on an RTX 4090:

    FP32 performance: 82.58 TFLOPS

    FP64 performance: 1.29 TFLOPS (1:64 rate)
    Using f32 on GPU drastically improves speed but introduces small numerical differences compared to CPU results.

Testing and Validation

All distance implementations in tsdistances are tested against AEON, a widely-used Python library for time series analysis and distances. This ensures that the results are correct and consistent with established benchmarks in the field.

To run the correctness tests, simply use pytest:

pytest -v tests/test_correctness_cpu.py