🤖 machine learning

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

The paper introduces QSMP, a novel method that combines Quick Shift and the Matrix Profile to efficiently identify representative time series subsequences for summarization and visualization with superior space complexity compared to state-of-the-art approaches.

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

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Time series data is the record of how something changes over time, a continuous stream of numbers that captures the pulse of the world. From the electrical sparks of a human brain to the ground shaking during an earthquake, these streams are often so long and complex that they overwhelm our ability to see what is actually happening inside them. Scientists have long sought a way to find the "representative" shapes hidden within these endless flows—specific patterns that repeat and tell a story about the system's state. The challenge is that these patterns are not always identical; they can shift in time, vary in speed, or appear slightly different each time they occur. Finding them requires sifting through millions of data points to locate the few shapes that matter most, a task that has traditionally been slow, computationally expensive, or prone to missing the very signals researchers are looking for.

In a new approach, researchers have developed a method called QSMP to solve this problem of finding representative waveforms in very long time series. The team, working across institutions in the United States, created a system that acts like a highly efficient filter, scanning through massive datasets to identify the most common and significant shapes without getting bogged down by the sheer volume of information. Their method combines two existing ideas: one that looks for the "densest" areas where data points cluster together, and another that quickly finds the closest matches between different parts of a time series. By weaving these together, they built a tool that can handle datasets with millions of samples, a scale that previously made such detailed analysis impossible.

The core of their discovery lies in how they treat the data. Instead of trying to compare every single moment in a long recording to every other moment—a process that would take an impractical amount of time and computer memory—they use a clever shortcut. They break the long stream into smaller, overlapping windows, treating each window as a distinct shape. Then, they look for the "hubs" where many of these shapes are very similar to one another. These hubs represent the most common patterns, or "modes," in the data. The researchers' innovation is that they can find these hubs while ignoring the trivial matches that naturally occur when a window is compared to its immediate neighbor, and they can also account for patterns that are slightly shifted in time. This allows the system to recognize that a spike in a brain signal is the same event even if it happens a fraction of a second earlier or later than expected.

To test their method, the team first used a synthetic dataset designed to mimic the complex, unpredictable nature of real-world signals like brain activity. They created a long time series by stitching together thousands of different wave shapes, ranging from slow, rolling waves to rapid, sharp spikes. When they ran their new algorithm against this data, it successfully identified all six distinct types of waves they had hidden inside, recovering nearly every frequency with high accuracy. In contrast, other existing methods struggled, often missing the rarer, faster patterns or confusing them with the more common, slower ones. The new method not only found the correct shapes but also preserved their exact form, whereas other approaches tended to smooth them out or average them into a generic shape that didn't truly represent any single event.

The researchers then applied their tool to real-world data from a patient with epilepsy, using recordings of electrical activity from the surface of the brain. These recordings contained hours of data, including periods just before seizures and periods of normal activity. The goal was to see if the algorithm could find the specific, sharp wave patterns known to be associated with seizure activity. The method succeeded in surfacing these high-frequency, sharp "spikes" and "spike-and-wave" patterns, which are critical for doctors to understand the condition. It found these distinct shapes with a level of detail that other methods missed, revealing the raw, jagged nature of the brain's electrical storms rather than blurring them into a smooth, unrecognizable curve.

A key advantage of this new approach is its efficiency. While previous methods required massive amounts of computer memory that made them unusable for the longest datasets, this new system uses a fraction of the space, allowing it to run on standard hardware or be accelerated by multiple graphics processors. This means that scientists can now analyze hours of continuous monitoring data in minutes rather than days. The method also offers flexibility; once the initial analysis is done, researchers can adjust the settings to see different levels of detail, choosing to find a few broad categories of patterns or many specific, nuanced variations without having to re-run the entire calculation.

The results suggest that this tool provides a powerful way to summarize and visualize the most important events in long streams of data. By finding the true, representative shapes rather than mathematical averages, it gives experts a clearer picture of what is happening. In the case of the epilepsy data, this means doctors can see the exact morphology of the warning signs before a seizure, which could be vital for developing better detection systems. The researchers emphasize that while the tool identifies these patterns, it is up to human experts to interpret their clinical significance, but the method ensures that the raw data is presented in its most honest and recognizable form. Through this work, the team has provided a way to turn the overwhelming noise of long time series into a clear, organized map of the events that truly matter.

Technical Summary of QSMP: Finding Representative Time Series Subsequences Through Quick Shift + Matrix Profile

Problem Statement
The paper addresses the challenge of identifying representative waveforms (subsequences) within long time series datasets. While existing methods like motif discovery can find recurring patterns, they often fail to quantify how much of the time series a candidate waveform covers. Conversely, density-based clustering methods that estimate the coverage of patterns often suffer from prohibitive computational complexity ( $O(N^2)$ space), rendering them infeasible for long time series (e.g., millions of samples). Additionally, approximate methods that use non-overlapping candidates may miss representative subsequences that span across window boundaries. The goal is to find a method that is scalable, exact (analyzing all windows), and capable of shift-invariant clustering to summarize and visualize large datasets for downstream tasks like classification and forecasting.

Methodology: QSMP
The authors propose QSMP (Quick Shift + Matrix Profile), a density-guided clustering algorithm designed to find representative waveforms as the modes of a probability density estimate derived from all subsequences.

Core Algorithm (Quick Shift Adaptation):
- QSMP adapts the Quick Shift algorithm, a mode-seeking clustering method, to time series. It constructs a directed acyclic graph (an anti-arborescence) where each subsequence (node) points to its nearest neighbor with a higher density.
- Clusters are formed by cutting edges in this tree where the distance to the higher-density neighbor exceeds a threshold $\tau$ . The node with the highest density in each resulting subtree is designated as the "mode" or representative waveform.
- Unlike Mean Shift, Quick Shift operates in a single iteration, connecting points directly to their higher-density neighbors.
Key Modifications for Time Series:
To make Quick Shift effective for time series, the authors introduce five specific modifications:
- Exclusion Zone: Trivial matches (overlapping windows starting at neighboring time points) are ignored by setting their distance to infinity.
- Centeredness Weighting: To prevent windows capturing only fragments of a pattern (e.g., at the edges of a subsequence) from becoming modes, the kernel width is locally adjusted based on a "centeredness" factor. Windows capturing full waveforms are weighted higher than those capturing fragments.
- Handling Missing Data: Subsequences near splice points of concatenated data segments are discarded to prevent artifacts.
- Shift Invariance: To handle temporal misalignment, the distance metric is modified using a min-pooling filter of length $B$ . The distance between two subsequences is the minimum distance found within a local lag window, allowing for partial matching and temporal shifts.
- Post-Processing: After tree cutting, subtrees with roots within the exclusion zone are merged to ensure contiguous segments are not split artificially.
Efficient Computation (Matrix Profile Integration):
- Standard density estimation requires $O(N^2)$ pairwise distance calculations, which is memory-intensive. QSMP leverages the Matrix Profile framework and the STOMP algorithm to compute the necessary distances and nearest-neighbor indices efficiently.
- By utilizing the recursive property of dot products in z-normalized Euclidean distance, the algorithm computes the distance matrix and the NN-index vector with a time complexity of $O(N^2(B+3))$ and a space complexity of $O(N)$ .
- The method is designed for multi-GPU acceleration, allowing the parallel computation of density estimates and nearest neighbors.

Key Contributions

Scalability: QSMP achieves linear space complexity ( $O(N)$ ) and near-quadratic time complexity, making it feasible for time series with millions of samples, unlike previous density-based methods that require $O(N^2)$ space.
Exactness: The method analyzes all overlapping windows, avoiding the risk of missing representative patterns that span across non-overlapping candidate windows used in approximate algorithms.
Shift-Invariant Clustering: The integration of min-pooling allows the algorithm to cluster subsequences that are similar but temporally shifted, a critical feature for biological and physical signals.
Post-Hoc Flexibility: Once the QS-tuple (density, NN-distance, NN-index) is computed, users can explore different clustering resolutions by varying the threshold $\tau$ and kernel width $\sigma$ without recomputing the expensive distance matrices.

Experimental Results
The authors evaluated QSMP on both synthetic and real-world datasets:

Synthetic Power-Law Dataset: QSMP was tested on a series of Morlet wavelets with varying frequencies. It outperformed Snippet-Finder and shift-invariant k-means (sikmeans) in recovering all six known frequencies with higher morphological fidelity (Cosine Similarity) and lower peak-frequency error.
Real ECoG Data (Study019): Applied to epileptic electrocorticography (ECoG) recordings, QSMP successfully identified high-frequency "sharp spikes" and "spikes and waves" associated with seizure activity. In contrast, sikmeans produced smoother, averaged centroids that obscured these sharp, high-frequency morphologies.
MixedBag Benchmark: On a downstream task involving change-point detection, QSMP achieved a success rate (82.0%) competitive with Snippet-Finder (84.0%) and significantly outperformed sikmeans (38.0%) and random sampling, despite having a much smaller space footprint.
Efficiency: A single run on the MixedBag dataset took approximately 15 minutes on a single GPU for QSMP, compared to over 8 hours for the CPU-based Snippet-Finder.

Significance and Claims
The paper claims that QSMP provides a valuable tool for the visual and exploratory discovery of representative patterns in very long time series. Its primary significance lies in its ability to balance computational efficiency with the exactness of analyzing all subsequences.

For Domain Experts: The method returns actual raw subsequences rather than averaged centroids, allowing experts (e.g., neurologists) to visualize the raw morphology and its specific temporal location.
Parameter Selection: The framework reduces the burden of hyperparameter tuning; the QS-tuple can be computed once, and different clustering granularities can be explored post-hoc by adjusting the distance threshold $\tau$ .
Limitations: The authors note that while QSMP surfaces recurrent morphologies, confirming their clinical or scientific significance requires downstream validation by domain experts, which is beyond the scope of the algorithm itself.

More like this