Abstract
Motif discovery is a core primitive of exploratory data analysis, aimed at finding recurring patterns in time series. However, the duration of a pattern is often unknown. To address this, an interval of window lengths is defined, requiring existing methods to try every length within that interval. Current pan matrix profile (PMP) approaches compute one z-normalized matrix profile per length, leading to $L$ quadratic self-joins for $L$ lengths.
We introduce Panache, the first one-pass streaming algorithm for z-normalized PMP motif discovery. It replaces repeated self-joins with a single scan whose runtime is near-linear in the series length. The key insight is that mean-centering a subsequence only alters its DC Fourier coefficient, allowing the non-DC spectrum of each z-normalized subsequence to be maintained online using sliding-DFT recurrences and running statistics. This spectral state enables similar subsequences to collide in an occupancy-controlled hash directory, and through Parseval's theorem, provides a lower bound that rejects most colliding pairs before any exact computation.
Panache computes every data-dependent parameter automatically, leaving only a resource budget to tune. At the default budget, it recovers all top-20 pan-motifs against exact fixed-exclusion ground truth on 17 UCR configurations and outperforms every CPU and GPU baseline benchmarked in this paper. On Wafer with five million samples across 51 lengths, Panache completes one pass in 2.9 minutes and emits exact motifs in 6.0 minutes, compared to 7.95 hours for the fastest exact CPU baseline and 38.3 minutes for SCAMP on an H100 GPU.
Blogger's Review: The design of the Panache algorithm breaks through traditional multi-join methods, significantly enhancing the efficiency of motif discovery with a one-pass streaming approach. Its advantages in resource usage and runtime provide a novel solution for large-scale time series analysis, warranting widespread attention and application.