🤖 AI

Panache: One-Pass Motif Discovery at Every Window Length

This paper introduces Panache, a novel one-pass streaming algorithm that achieves near-linear time complexity for z-normalized pan-motif discovery across all window lengths by maintaining online spectral states to efficiently filter candidates, significantly outperforming existing CPU and GPU baselines in both speed and accuracy.

Original authors: Tej Sanibh Ranade

Published 2026-07-21

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Tej Sanibh Ranade

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

Imagine you are a detective trying to find a specific, repeating sound in a massive, hours-long recording of a busy city street. You know the sound happens over and over, but you have no idea how long it lasts. Is it a short, sharp "beep"? A long, drawn-out "hum"? Or maybe a medium-length "chirp"? If you try to find it by listening to the whole recording over and over again, once guessing it's a beep, then again guessing it's a hum, and again guessing it's a chirp, you'd be there forever. This is the daily struggle of data scientists working with time series—lists of numbers that change over time, like heartbeats, stock prices, or earthquake tremors. They want to find motifs: the hidden, repeating patterns that tell a story. The tricky part is that they rarely know the "duration" (how many seconds or data points the pattern lasts) in advance. To solve this, they usually have to check every possible length, which is like trying to find a needle in a haystack by checking every single straw one by one, over and over again.

Enter Panache, a new method that acts like a super-smart, one-pass detective. Instead of stopping the tape to rewind and check different lengths, Panache listens to the recording just once. As the sound flows in, it instantly figures out the repeating patterns at every possible length simultaneously. It does this by turning the sound into a "spectral fingerprint"—a unique signature based on the shape of the waves rather than just their volume. If two sounds look similar, their fingerprints match, and Panache knows to investigate them further. If they don't match, it ignores them immediately. The result? It finds the exact same patterns as the old, slow methods but does it in a fraction of the time. In tests, while other methods took hours to analyze a massive dataset, Panache finished in minutes, proving that you don't need to repeat the work to get the right answer.

The Problem: The "Goldilocks" Window

In the world of time-series data, a "motif" is a pattern that repeats. But a pattern isn't just a shape; it's a shape plus a duration. Imagine trying to find a specific dance move in a video. If you look at a window that is too short, you only see a foot tap. If you look at a window that is too long, you see the foot tap mixed with the next move, the background, and the dancer's outfit. You need the "Goldilocks" window: just the right length to see the whole move clearly.

The problem is that in exploratory data analysis, we often don't know what that "just right" length is. We might need to check lengths from 10 points to 1,000 points. The old way of doing this, called the Pan Matrix Profile (PMP), was like a very thorough but incredibly slow librarian. To find the best match for every length, the librarian had to run a separate, massive search for length 10, then start over for length 11, then length 12, and so on. If you had 50 different lengths to check, the librarian had to read the entire book 50 times. This is called doing "quadratic self-joins," which is a fancy way of saying "comparing every piece of data to every other piece of data, over and over again." It works, but it gets painfully slow as the data gets bigger.

The Panache Solution: One Pass, All Lengths

The authors of this paper, Tej Sanibh Ranade, introduced Panache, which is the first algorithm to do this "Pan Matrix Profile" job in a single pass. Instead of rewinding the tape 50 times, Panache reads the data stream exactly once. As each new number arrives, it updates its internal state for all the different lengths it cares about at the same time.

How does it pull off this magic trick? It relies on a clever observation about math. When you take a chunk of data and "normalize" it (which means adjusting it so it has an average of zero and a standard deviation of one, effectively removing the volume and focusing only on the shape), something amazing happens. The only part of the data's mathematical "spectrum" (its Fourier transform) that changes is the DC component (the average). The rest of the spectrum—the parts that describe the actual shape of the wave—stays exactly the same, regardless of the average.

Panache uses this fact to maintain a sliding spectral state. As the window of data slides forward one step, the algorithm doesn't re-calculate the whole shape from scratch. Instead, it uses a "sliding DFT" (Discrete Fourier Transform) recurrence. Think of it like a conveyor belt of ingredients. When a new ingredient arrives, you don't throw away the whole recipe and start over; you just swap out the old ingredient at the back and add the new one at the front, adjusting the math slightly. This allows Panache to keep an up-to-date "fingerprint" of the shape for every window length in real-time.

The Detective's Toolkit: Hashing and Rejection

Once Panache has these spectral fingerprints, it needs to find which ones match. It can't compare every single fingerprint to every other one, or it would still be too slow. So, it uses a Locality-Sensitive Hash (LSH). Imagine a giant filing cabinet where similar fingerprints are automatically sorted into the same drawer. If two windows have similar shapes, their hashes (digital signatures) will be very close, and they will land in the same bucket.

However, just because two things are in the same bucket doesn't mean they are a perfect match. To avoid doing expensive, exact calculations on every pair in the bucket, Panache uses a Parseval lower bound. This is a mathematical safety net. It calculates a "minimum possible distance" between two shapes based only on their spectral fingerprints. If this minimum distance is already too big to be a match, Panache throws the pair away without doing any further work. It's like a bouncer at a club who checks ID; if the ID looks fake, they don't even let you in the door to check your face. This step rejects the vast majority of "almost matches," saving huge amounts of time.

The "Anchor" Strategy

Even with these tricks, keeping track of every single possible length (say, from 10 to 1,000) in memory would be too much. So, Panache uses a strategy called Anchor Lengths. Instead of maintaining a full, active search for every single length, it only keeps the "active" search running for a few selected lengths (the anchors), spaced out like stepping stones.

The paper argues that motifs are "sticky." If a pattern is a good match at length 20, it's very likely to also be a good match at length 19 or 21. So, Panache finds the matches at the anchor lengths and then does a quick, local check on the lengths in between. This means it doesn't have to do the heavy lifting for every single length, but it still finds the answers because the "good" lengths are clustered together.

The Results: Speed and Accuracy

The authors tested Panache on 17 different configurations of real-world data, including heartbeats (ECG), earthquakes, and stock market data. They compared it against the best existing methods, including those running on powerful GPUs (graphics cards used for high-speed computing).

The results were striking. On a dataset called Wafer with 5 million data points and 51 different lengths to check:

The fastest existing CPU method took 7.95 hours.
A top-tier GPU method (Scamp on an H100) took 38.3 minutes.
Panache completed the initial scan in 2.9 minutes and emitted the final exact motifs in 6.0 minutes.

Panache was faster than every CPU and GPU baseline they tested. More importantly, it didn't sacrifice accuracy. It recovered 100% of the top-20 motifs that the exact, slow methods found. Every single pattern it reported was an exact distance to a valid neighbor, not an estimate.

Why This Matters

The paper concludes that Panache solves a long-standing problem in data mining: how to find repeating patterns of unknown length in a streaming, real-time fashion without sacrificing accuracy. By replacing the repetitive, slow "rewind and search" approach with a single, smart pass that uses spectral fingerprints and mathematical shortcuts, Panache makes it possible to analyze massive streams of data in minutes rather than hours. It proves that you can have your cake and eat it too: you can get the exact, rigorous results of the old methods with the speed of a modern streaming algorithm. The only trade-off is memory; because it keeps a lot of data in RAM to do these quick lookups, it requires more memory than some simpler methods, but for the speed it delivers, the authors suggest it's a worthwhile price.

Technical Summary: Panache – One-Pass Motif Discovery at Every Window Length

1. Problem Statement

Time-series motif discovery seeks recurring patterns within a sequence. A fundamental challenge in this domain is that a "pattern" is defined by its duration (window length, $m$ ), which analysts often cannot specify in advance. Traditional approaches define an interval of window lengths $[m_{min}, m_{max}]$ and attempt to find motifs for every length within that interval.

Existing methods for the Pan Matrix Profile (PMP), which aggregates motif information across all lengths in an interval, suffer from a critical inefficiency: they treat each window length as an independent problem. To compute the PMP, existing algorithms perform $L$ separate quadratic self-joins (where $L$ is the number of lengths), effectively rescanning the entire time series for every single window length. This results in a computational cost that scales linearly with the number of lengths and quadratically with the series length, making it prohibitive for large datasets or real-time streaming applications.

The goal is to achieve one-pass, streaming motif discovery that computes the PMP for an interval of lengths without rescanning the data, while maintaining the guarantee of exact z-normalized distances.

2. Methodology: The Panache Algorithm

Panache introduces the first one-pass streaming algorithm for z-normalized PMP motif discovery. Instead of performing $L$ independent self-joins, Panache maintains a single multi-length search state as it scans the series once.

Core Mechanisms

The algorithm relies on four key mechanisms to scale with the stream:

Normalized AC Spectrum as Streaming State:
- Panache observes that z-normalizing a subsequence (subtracting the mean and dividing by the standard deviation) only affects the DC (zero-frequency) Fourier coefficient. The non-DC coefficients remain unchanged in shape, merely scaled by the standard deviation.
- The algorithm maintains an online state of the non-DC Fourier coefficients for every anchor length using sliding-DFT recurrences. As a new sample arrives, the oldest sample is removed, and the new one is added, updating the coefficients in $O(K)$ time (where $K$ is the retained spectral width).
- This spectral vector serves a triple purpose:
  - Streaming State: It updates incrementally.
  - SimHash Key: It acts as a Locality-Sensitive Hash (LSH) signature. Windows with similar normalized shapes have similar spectral vectors and thus collide in the same hash buckets.
  - Rejection Bound: Using Parseval's theorem, the algorithm computes a lower bound on the Euclidean distance between two windows based on their truncated spectral vectors. This bound allows Panache to reject the vast majority of candidate pairs before performing expensive exact distance calculations.
Anchor Lengths:
- Maintaining a full online index for every length in the interval is memory-intensive. Panache selects a subset of anchor lengths (e.g., every $s$ -th length) to maintain online indexes.
- It relies on the empirical observation that motifs persist across neighboring lengths. If a motif is found at an anchor length, the algorithm performs a local completion step to verify and refine the motif at the non-anchor lengths in the immediate neighborhood.
Occupancy-Controlled Hashing:
- To handle the growing stream without unbounded memory growth, Panache uses a global-depth prefix directory (a variant of extendible hashing).
- It controls bucket occupancy by splitting the directory globally when the population exceeds a target threshold ( $\alpha$ ). This ensures that the number of candidates to inspect per query remains bounded, regardless of the stream length.
- Multi-probing is used to handle hash collisions, inspecting buckets at Hamming distance 1 to ensure high recall.
Emit-Time Completion:
- The streaming pass produces a "sound upper pan-profile" (an upper bound on the true profile). To ensure exactness, a final emit stage runs after the stream:
  - Hot-Class Sieve: For hash buckets that exceed the verification budget (containing many similar windows), a sorting-based sieve evaluates exact distances among the most promising candidates.
  - Local Completion: For non-anchor lengths, the algorithm takes the best motifs found at anchor lengths as "seeds" and performs exact distance computations in their local neighborhoods (in length and position) to fill in the gaps.

Determinism and Parallelism

Panache processes data in micro-batches. Within a batch, windows are advanced in parallel, and exact distance computations are buffered. A fixed merge order ensures that the output is deterministic regardless of the number of threads or the specific schedule of execution.

3. Key Contributions

One-Pass Formulation: Panache is the first algorithm to compute a z-normalized PMP in a single pass over the data, replacing $L$ quadratic self-joins with a single linear scan.
Spectral State Representation: It introduces a normalized AC-spectrum representation that is maintained online, serving simultaneously as the streaming state, the LSH key, and the source of a Parseval lower bound for pruning.
Scalable Mechanisms: The paper details the integration of occupancy-controlled global-depth hashing, anchor-length search, and deterministic batched updates to handle large streams.
Exactness Guarantee: Unlike many streaming approximations, Panache guarantees that every written cell in the profile is an exact z-normalized distance to a valid neighbor. It does not report estimated distances.

4. Experimental Results

The algorithm was evaluated on 17 configurations across 10 UCR time-series datasets, ranging from 1,600 to 5 million samples, with window lengths spanning 30 to 80.

Recovery Accuracy: Panache recovered 100% of the top-20 motifs (340/340 against Stumpy ground truth; 740/740 across the full benchmark) with exact distances.
Performance vs. CPU Baselines: Panache is significantly faster than existing exact CPU baselines (Scamp, Stumpy, SCRUMP).
- Median speedup: 6.6x over Scamp CPU and 7.3x over Scamp-GPU.
- On the Wafer 5M dataset (5 million samples, 51 lengths), Panache completed the streaming pass in 2.9 minutes and emitted exact motifs in 6.0 minutes.
- In contrast, the fastest exact CPU baseline (Scamp) took 7.95 hours, and Scamp on an H100 GPU took 38.3 minutes.
Memory Efficiency: While the algorithm requires linear memory in the series length (to store features and the profile), it remains practical. For the 5M sample run, peak memory was 23.3 GB during the stream and 35.5 GB at full materialization.

5. Significance and Claims

The paper claims that Panache resolves the long-standing trade-off between streaming efficiency and multi-length coverage. Previous methods could either stream a single length or compute multiple lengths offline with high cost. Panache achieves both:

It processes the full interval of lengths in one pass.
It maintains exactness (no probabilistic approximations in the final output).
It is data-dependent in its parameter selection (e.g., spectral width $K$ is calibrated from the data), requiring only a single resource budget ( $\alpha$ ) to be tuned by the user.

The authors emphasize that the algorithm's speedup comes not from sacrificing accuracy, but from eliminating redundant rescans and leveraging the mathematical properties of z-normalized spectra to prune the search space efficiently. The work demonstrates that "one-pass" and "exact" are compatible for the Pan Matrix Profile problem.