gap_significance

Code and experiment scripts for the paper "Automatic threshold selection for multivariate time series pattern matching", introducing the Gap-Significance (GS) method: an unsupervised, parameter-free way to pick a distance threshold for time-series pattern matching, compared against the $n\sigma$ rule and the $L$-trend method on the UCR Time Series Archive.

The paper itself (LaTeX sources, figures, submission templates) lives under assets/. This README only covers how to install the library and reproduce the experiments.

Installation

Requires Python >= 3.12.

pip install -e .
# or, with uv
uv sync

Core dependencies: stumpy, dtaidistance, dtw-python, scipy, scikit-learn, numpy, pandas. See pyproject.toml for the full list.

Repository layout

smaipm/                 # Library: GS algorithm, distances, calibration, filters
distance.py             # Standalone distance-profile / GS helpers used by the benchmark scripts
scripts/                # Benchmark experiments (UCR archive)
compress_datasets.py    # UCR TSV -> NPZ conversion
precompute_norm.py      # Precompute z-normalized Euclidean distance matrices
precompute_dtw.py       # Precompute DTW distance matrices
notebooks/               # Analysis notebooks that turn benchmark results into paper figures/tables
data/                    # UCR datasets (NPZ) + benchmark result files (parquet)
tests/                   # Unit tests for the distance/GS implementations

Reproducing the experiments

1. Data

The experiments use the UCR Time Series Classification Archive. Download and extract it, then convert the per-dataset *_TRAIN.tsv / *_TEST.tsv files to compressed NPZ (float32 data, int16 labels):

python compress_datasets.py -i /path/to/UCRArchive_2018 -o data/ --execute

Datasets already provided as data/<Name>/<Name>_TRAIN.npz and _TEST.npz in this repository can be used as-is; re-running this step is only needed to regenerate them from scratch.

2. Precompute distance matrices

The controlled/sliding benchmarks reuse full pairwise distance matrices to avoid recomputation. These must exist before running the benchmark scripts:

# z-normalized Euclidean distance (used for the sigma / GS comparisons)
python precompute_norm.py -i data/ --execute -w 4

# DTW distance
python precompute_dtw.py -i data/ --execute -w 4

Both scripts default to a dry run (no --execute) so you can check estimated sizes first; use --dataset <Name> to run on a single dataset.

3. Run the benchmarks

Three complementary experimental protocols are implemented in scripts/. Each is incremental (resumable) and writes a parquet file under data/.

# Distance-matrix based comparison: GS threshold vs 2-sigma vs 3-sigma
python scripts/ucr_compare.py --max-total 500

# Controlled class-balance benchmark: K in-class samples vs 50*K out-of-class samples
python scripts/ucr_controlled_benchmark.py --k-per-class 5 --method stumpy

# Sliding-window benchmark on concatenated series
python scripts/ucr_sliding_benchmark.py --max-queries 10 --method stumpy

Useful flags common to all three: --dataset <Name> to run a single dataset for debugging, --force to recompute and overwrite existing results, --seed for reproducibility. Run <script> --help for the full list.

Results are appended to:

• data/ucr_compare_results.parquet
• data/ucr_controlled_benchmark_results.parquet
• data/ucr_sliding_benchmark_results.parquet

4. Generate figures and tables

Open the corresponding notebook in notebooks/ to turn each result file into the tables/plots used in the paper:

• ucr_compare_results.ipynb — GS vs sigma-threshold comparison
• ucr_controlled_results.ipynb — controlled class-balance results
• benchmark_results.ipynb — sliding-window benchmark results
• freezer_deep_analysis.ipynb — qualitative deep dive on FreezerRegularTrain
• bench_expected_gaps.ipynb — validates the theoretical expected-gap-width formula (Section 3) against Monte Carlo simulation for several distributions

Exported figures are saved to assets/img/, matching the ones referenced in the paper's LaTeX sources under assets/tex/.

Tests

pytest

Using the library

The high-level entry point is smaipm.indicators.stumpy_indicator, which runs pattern matching with an automatically selected GS threshold:

from smaipm.indicators import stumpy_indicator

result = stumpy_indicator(series, query)

See smaipm/utils.py for the core GS routines (get_gap_series, heuristic_thresholds) and smaipm/calibration.py for learning channel weights in the multivariate setting.