PaperlayerView exact revision on arXiv

Source-linked AI summary

QSMP: finding representative time series subsequences through Quick Shift+Matrix Profile

Carlos H. Mendoza-Cardenas, Rogers F. Silva, Austin J. Brockmeier

arXiv:2608.15492v1cs.LG

TL;DR

Existing motif-discovery methods do not account for how much of a long time series a candidate waveform represents. QSMP addresses this gap by clustering all subsequences with a density-guided Quick Shift–Matrix Profile method, and experiments show it recovers representative waveform morphologies in synthetic and ECoG data.

  • Problem

    Existing motif-discovery methods identify recurring waveforms without accounting for how much of the time series each candidate represents.

  • Method

    QSMP uses hierarchical, density-based, shift-invariant clustering with Matrix Profile techniques to efficiently find modes among all time-series subsequences.

  • Results

    Across synthetic and ECoG experiments, QSMP recovered known or recurrent waveform morphologies, including seizure-related sharp spikes and spikes-and-waves.

  • Takeaways & Limitations

    QSMP provides raw representative subsequences with their temporal locations, supporting visualization and inspection of waveform patterns in very long time series.

  • Takeaways & Limitations

    QSMP surfaces recurrent morphologies for expert inspection, but their clinical significance requires downstream validation beyond this study.

Abstract

from arXiv · show

Finding representative waveforms in long time series has scientific and practical value in many domains, as it enables summarization and visualization of large time series datasets, and downstream tasks like classification and forecasting. We present here QSMP, a method to find representative waveforms in long time series through a density-guided clustering of time series subsequences. Our method makes a novel connection between Quick Shift, a mode-seeking algorithm, and the Matrix Profile, a time series similarity-search data structure, to adapt Quick Shift to the clustering of subsequences in long time series, with a space complexity that is superior to the state-of-the-art method. Our experiments on synthetic and real datasets show that QSMP can be a valuable tool to summarize and visualize long time series by finding representative waveforms.

1. INTRODUCTION

The introduction motivates representative waveform discovery as a way to connect recurring time-series shapes with variables of interest and identifies coverage-aware clustering as a challenge for long recordings. It presents QSMP, an exact, scalable, density-based method that uses Quick Shift and Matrix Profile techniques to cluster subsequences and select representative modes.

  • Motivation: Representative waveforms can relate time-series shape to variables such as disease state, insect feeding patterns, and earthquake source.A waveform is defined as representative when it can sufficiently approximate the relevant signal behavior, although the supplied passage is truncated before the full definition.
  • Problem: Motif-discovery methods find recurring waveforms but do not account for how much of the time series a candidate waveform covers.Coverage is central to identifying representative subsequences rather than merely repeated patterns.
  • Contribution: QSMP defines representative waveforms as modes of a density estimate over all subsequences, improving scalability for long time series.The method combines Quick Shift with Matrix Profile techniques to form density estimates efficiently.
  • Method: QSMP performs shift-invariant, hierarchical density-based clustering of time-series subsequences using computational techniques from STOMP.Each length-m window is represented as a point in R^m; dense clusters yield modes as their most representative waveforms.
  • Contribution: QSMP analyzes all windows exactly, avoiding the pairwise-distance burden of standard hierarchical clustering and the candidate omissions of approximate methods.Approximate methods use non-overlapping subsequences as candidates, whereas QSMP evaluates every window.

2. RELATED WORK

Prior work has used density-based mode seeking, Matrix Profile distances, and shift-aware clustering to identify representative time-series patterns. These approaches respectively generate meaningful patterns, greedily select snippets, or average subsequences into centroids that may not reflect actual waveforms.

  • Density-based pattern discovery: An early method combines weighted kernel density estimation with mean-shift to cluster time-series subsequences and find meaningful patterns.It generates candidate random-walk noise subsequences from a discrete random-walk model before weighting the data by similarity.
  • Matrix Profile-based summarization: Snippet-Finder uses MPdist-based distance profiles and greedily selects k representative snippets minimizing the area under their minimum-profile curve.MPdist compares two time series through the similarity of their subsequences.
  • Shift-aware clustering: Shift-aware k-means variants such as sikmeans and k-shape approximate representative-waveform discovery, but their averaged centroids may not accurately reflect actual subsequences.Their centroids are averages by definition.

3. METHODS

QSMP adapts Quick Shift to cluster time-series subsequences into representative waveforms by building a density-guided tree and segmenting it with a distance threshold. It efficiently computes the required subsequence relationships with Matrix Profile techniques while incorporating modifications for trivial matches, waveform centeredness, missing data, and temporal shifts.

  • Quick Shift clustering: Quick Shift links each subsequence to its nearest higher-density neighbor, forming a directed tree whose threshold-based subtrees define clusters and representative waveforms.Cutting edges longer than τ creates rooted trees, with each subtree root serving as a representative waveform.
  • Quick Shift clustering: σ controls density-estimation scale, while τ controls tree segmentation and can be selected by binary search to obtain a desired number of modes.Because z-normalized Euclidean distance is unit-invariant, σ ≈1 is a sensible starting point.
  • QSMP modifications: QSMP modifies Quick Shift by excluding trivial matches, down-weighting off-center waveform fragments through centeredness, and suppressing subsequences near missing-data splice locations.The centeredness factor lowers the density of poorly centered windows, while splice suppression prevents neighboring concatenated segments from being selected.
  • Efficient computation: O(N 2(B + 3)) time and O(N) space complexity result from adapting STOMP to compute the QS-tuple (˜f, d, v), with GPU parallelism used for acceleration.B < m is the min-pooling filter length used for shift invariance.

4. EXPERIMENTS AND RESULTS

Experiments on synthetic power-law data, epileptic ECoG recordings, and the MixedBag benchmark evaluate QSMP’s recovery, waveform diversity, and downstream motif quality. QSMP recovers rare high-frequency synthetic patterns, surfaces diverse ECoG morphologies, and performs competitively on regime-separation success despite lower space complexity.

  • Synthetic power-law dataset: QSMP, sikmeans, and Snippet-Finder were evaluated with m = 512 and k = 6 using unsupervised, method-specific hyperparameter selection and recovery scoring over 20 random realizations.Returned patterns were matched with replacement to the closest known prototype using a shift-invariant distance.
  • Synthetic power-law dataset: QSMP cleanly recovers all six synthetic frequencies, whereas Snippet-Finder and sikmeans duplicate prevalent low frequencies and miss rare high frequencies.The synthetic series used six 1-second Morlet wavelets at 1, 5, 12, 30, 100, and 150 Hz, sampled at 512 Hz.
  • ECoG data: On Study019 epileptic ECoG data, QSMP recovers several high-frequency patterns despite low-frequency dominance from the 1/f power spectral density.QSMP used subsequences of m = 512, corresponding to 1 second.
  • ECoG data: In qualitative comparison on Study019-preictal data, QSMP returns raw patterns that are more sensitive to morphology changes, while sikmeans produces smoother averaged patterns.The comparison used m = 512 and k = 128; Snippet-Finder could not be run.
  • MixedBag benchmark: On MixedBag, QSMP is competitive with Snippet-Finder and far above sikmeans and random sampling in success rate, while using much smaller space complexity.Success means the two QSMP modes fall in different regimes, with each method’s remaining hyperparameter selected by its own unsupervised criterion.

5. CONCLUSION · A. DETAILED QSMP ALGORITHMS AND GPU PARALLELISM

QSMP finds representative patterns in very long time series using linear space, quadratic time, and multi-GPU parallelization, with modes that are actual raw subsequences. Its detailed algorithms use rolling inner-product updates, GPU-parallel row computation, density estimation, and shift-invariant nearest-neighbor search.

  • 5. CONCLUSION: QSMP finds representative patterns in very long time series with linear space complexity, quadratic time complexity, and multi-GPU parallelization.Its modes are actual subsequences from the raw time series.
  • 5. CONCLUSION: QSMP enables visualization of raw representative patterns and their temporal locations, which is desirable for domain experts such as neurologists examining EEG.Both the raw patterns and their temporal locations are available from QSMP.
  • A. DETAILED QSMP ALGORITHMS AND GPU PARALLELISM: The squared z-normalized distance D_i,j depends on subsequences through the inner product ρ_i,j = x_i^T x_j.Each ρ_i,j follows from ρ_i−1,j−1 in O(1) time.
  • A. DETAILED QSMP ALGORITHMS AND GPU PARALLELISM: The whole inner-product row ρ_i is obtained from ρ_i−1 in O(N) time using two buffers that split N output cells across GPU threads.The buffers ρ_in and ρ_out hold rows i−1 and i, respectively.
  • A. DETAILED QSMP ALGORITHMS AND GPU PARALLELISM: The rolling inner-product update uses a precomputed vector ρ_1 and two iteration buffers to enable parallelization and GPU acceleration.Figure 6 illustrates the update for i = 2 and j = 2, . . . , N with two GPU threads.
  • A. DETAILED QSMP ALGORITHMS AND GPU PARALLELISM: Algorithm 1 assembles the density estimate in a single O(N^2) pass over rolling inner products, using rolling means, standard deviations, and FFT-based precomputation of ρ_1.computeDistance evaluates D_i,j from ρ_i,j and the rolling statistics.
  • A. DETAILED QSMP ALGORITHMS AND GPU PARALLELISM: Algorithm 2 computes shift-invariant NN-distance d and NN-index v by applying length-B min-pooling before the higher-density nearest-neighbor search.The total cost is O(N^2(B + 3)) time and O(N) space.

B. EXTENDED RECOVERY EXPERIMENTS: WAVELETS WITH POISSON PROCESS ACTIVATION

This section stress-tests QSMP and two other methods on a harder wavelet-recovery dataset with Poisson-distributed activations, frequent overlaps, and superposition. Performance is reported as mean ± 95% CI over 20 seeds.

  • Experimental setup: The experiment compares three methods on a harder wavelet-recovery variant where 1,000 wavelet arrivals follow a Poisson process.Activation times are uniformly distributed rather than tiled edge-to-edge.
  • Experimental setup: About 63% of consecutive activations overlap, causing neighboring wavelets to frequently overlap and superimpose.This creates a more challenging recovery setting than the clean-wavelet arrangement in the main text.
  • Evaluation: Performance is summarized as the mean ± 95% CI over 20 seeds.The reported aggregation reflects repeated experiments across independent seeds.

B.1. Quantitative recovery

The quantitative evaluation measures frequency recovery, prototype morphology fidelity, and peak-frequency error. QSMP matches Snippet-Finder in recovered frequencies but achieves higher morphology fidelity, while sikmeans recovers only half of the patterns on average.

  • Quantitative metrics: Table 3 evaluates methods using FreqRec, CosSim, and PeakErr, with prototypes matched to ground truth with replacement.FreqRec counts distinct frequencies recovered out of six; CosSim measures shift-invariant cosine similarity, and PeakErr measures mean peak-frequency error.
  • Quantitative recovery: QSMP and Snippet-Finder tie on recovered frequencies, with a paired-test p-value of 0.87.The comparison concerns the number of frequencies recovered.
  • Morphology fidelity: CosSim is 0.83 for QSMP versus 0.77 for Snippet-Finder, a significant morphology-fidelity advantage for QSMP.The paired t-test gives p = 0.035, with Cohen’s dz = 0.51.
  • Quantitative recovery: sikmeans recovers only three of the six patterns on average because low-frequency prevalence overwhelms it.This indicates reduced recovery under the evaluation’s six-pattern setting.

B.2. Qualitative recovery and failure modes

On an automatically selected representative seed, QSMP and Snippet-Finder recover most frequencies, while sikmeans misses rare high frequencies and collapses centroids onto prevalent low frequencies. The figures visualize these method-specific recovery patterns against shift-aligned ground truth and aggregate recovery across 20 seeds.

  • Representative seed selection: The per-seed figures use a seed automatically selected to be jointly typical of all three methods, rather than favorable to any one method.Selection minimizes the total absolute deviation between each method’s per-seed FreqRec values and its own 20-seed mean.
  • Qualitative recovery: On the representative seed, QSMP and Snippet-Finder cover most frequencies in shift-aligned overlays with the ground truth.Figure 7 shows one column per frequency and the prototypes returned by each method.
  • Failure modes: sikmeans leaves rare high frequencies empty and stacks several centroids onto prevalent low frequencies.These patterns are described respectively as misses and ×n collapse in the qualitative overlays.
  • Aggregate recovery: Figure 8 aggregates per-frequency recovery rates across all 20 seeds.The figure complements the representative-seed visualizations with an across-seed summary.

B.3. Why Snippet-Finder trails on CosSim

Snippet-Finder matches QSMP in recovered-frequency count but trails on CosSim because MPdist rewards fragment-level agreement rather than whole-prototype morphology. This produces contaminated matches, weak recovery of rare frequencies, and lower performance even under Snippet-Finder’s own distance.

  • B.3. Why Snippet-Finder trails on CosSim: Snippet-Finder selects verbatim, non-overlapping windows by minimizing MPdist ProfileArea, which combines fidelity and coverage through fragment-level similarity.Here, MPdist compares sub-subsequences of length S = 154, or 30% of m.
  • B.3. Why Snippet-Finder trails on CosSim: MPdist can rate a window splicing half of a 100 Hz wavelet with half of a 12 Hz wavelet as a perfect match to both prototypes.Whole-window cosine instead penalizes this mixed morphology.
  • B.3. Why Snippet-Finder trails on CosSim: 22% vs. 13%: Snippet-Finder has roughly twice QSMP’s fraction of poor matches, despite identical median matched cosine of 0.972.Poor matches are defined as cosine < 0.5.
  • B.3. Why Snippet-Finder trails on CosSim: Snippet-Finder’s coverage objective barely credits the rarest 150 Hz frequency, which occupies ∼0.3% of the Poisson signal and remains unrecovered by its closest snippet.The selected snippet is a non-match for the 150 Hz prototype.
  • B.3. Why Snippet-Finder trails on CosSim: 3.29 vs. 4.55: QSMP still wins under Snippet-Finder’s own mean MPdist recovery score, with paired p = 0.003 and dz = 0.78.This indicates the gap is not caused by evaluating Snippet-Finder with whole-window cosine; it reflects its coverage-oriented objective.

B.4. Denoising returned prototypes by shift-aligned averaging

The study tests whether averaging the nearest signal occurrences of QSMP and Snippet-Finder prototypes can denoise their raw subsequences. Averaging helps common frequencies but can worsen prototypes for rare frequencies when unrelated windows enter the fixed top-10.

  • Raw prototypes: QSMP and Snippet-Finder return individual noisy signal subsequences as raw prototypes.The denoising test averages occurrences of each returned QSMP mode or Snippet-Finder snippet.
  • Averaging procedure: Nearest occurrences are located with a sliding-window z-normalised distance profile, shift alignment, trivial-match exclusion, and a fixed top-10.The selected windows are averaged to test whether repeated occurrences denoise the returned prototype.
  • Common frequencies: Cosine similarity for QSMP’s 5 Hz mode improves from 0.72 to 0.99 after averaging, while Snippet-Finder’s 1 Hz snippet improves from 0.95 to 0.99.These common-frequency occurrences are plentiful, so all ten windows are genuine and averaging cleanly denoises the waveform.
  • Rare frequencies: 150 Hz is activated only 3 times in this seed, causing seven of ten averaged windows to be unrelated or superimposed segments and making the average worse than the raw waveform.Thus, a fixed top-10 cannot rescue the rarest frequencies.

B.5. Limitation of unsupervised σ selection

QSMP selects the kernel width σ without supervision using a max-min diversity criterion over density modes. This criterion favors wide kernels, which can improve frequency recovery while causing redundant prototypes and missed rarer frequencies.

  • Unsupervised σ selection: QSMP selects σ by retaining the value whose k density modes are most mutually distinct under a max-min diversity criterion.The density modes are individual signal subsequences, and σ governs them.
  • Recovery trade-off: 4.91 vs. 4.44 on average: σ = 3 recovers slightly more frequencies than σ = 2, but wider kernels can collapse shape-distinct low-frequency modes onto one peak.This redundancy can cause a rarer frequency to be missed.

C. ADDITIONAL ECOG RESULTS (STUDY019 INTERICTAL)

On Study019 interictal data, QSMP and sikmeans show the same qualitative contrast reported for preictal data. QSMP returns sharper, higher-frequency epileptiform waveforms, whereas sikmeans produces smoother averaged centroids.

  • QSMP surfaces sharper, higher-frequency epileptiform morphologies in interictal data.Its modes are raw subsequences.
  • sikmeans returns smoother averaged centroids than QSMP on the interictal dataset.
  • Fig. 11 shows QSMP and sikmeans patterns in the Study019-interictal dataset.
Loading 2608.15492v1…