Panache: One-Pass Motif Discovery at Every Window Length

Tej Sanibh Ranade

cs.AIJul 20, 2026

Panache: One-Pass Motif Discovery at Every Window Length

Authors: Tej Sanibh Ranade

Organizations: Independent Researcher

Abstract

Motif discovery, the search for recurring patterns within a time series, is a core primitive of exploratory data analysis. A pattern, however, is defined by its duration, which analysts rarely know in advance. To resolve this unknown duration, an interval of window lengths is defined, and the accepted method is to try every length in that interval. Existing pan matrix profile (PMP) methods compute one z-normalized matrix profile per length, so $L$ lengths cost $L$ quadratic self-joins over the same series. We introduce Panache, to our knowledge the first one-pass streaming algorithm for z-normalized PMP motif discovery. It replaces the repeated self-joins with a single scan whose runtime is near-linear in the series length. The key observation is that mean-centering a subsequence changes only its DC Fourier coefficient, so the non-DC spectrum of every z-normalized subsequence can be maintained online by sliding-DFT recurrences and running statistics. This spectral state is the key under which similar subsequences collide in an occupancy-controlled hash directory and, through Parseval's theorem, yields a lower bound that rejects most colliding pairs before any exact computation. Panache computes every data-dependent parameter itself, 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 is faster than every CPU and GPU baseline benchmarked in this paper. On Wafer at five million samples over 51 lengths, Panache completes one pass in 2.9 minutes and emits the exact motifs in 6.0 minutes, against 7.95 hours for the fastest exact CPU baseline and 38.3 minutes for SCAMP on an H100 GPU.

Explore similar work

Jul 3, 2026cs.DB

Scalable Maximal Frequent Episode Mining with Desbordante

Episode mining aims to extract subsequences of events that possess certain distinctive properties and constitute facts valuable to the user. Maximal frequent episode mining concentrates on discovery of frequently-appearing subsequences, which are not included into any other larger frequent subsequence. The state-of-the-art for this problem is the MaxFEM algorithm which enumerates possible subsequences, while applying various pruning techniques to accelerate the search. However, this is a computationally-intensive problem: reducing the minimum number of required subsequence occurrences or increasing the length of the subsequence both substantially raise running time, which limits practical use of MaxFEM. In this paper we describe our efforts in designing a high-performing algorithm for this problem. For this we: 1) develop an efficient C++ implementation of MaxFEM, and 2) devise an efficient technique to parallelizing it. As the result, we propose an improved parallel MaxFEM variant, which we call ParMaxFEM. Additionally, we integrate the improved algorithm into Desbordante - a high-performance, open-source data profiler with deep Python integration that treats patterns as first-class entities and allows users to develop their custom programs that can include discovery and validation of patterns. To evaluate our approach we compare both C++ implementations with the original SPMF implementation. Experiments demonstrated that our reimplemented version provides up to

8\times

speedup over the SPMF baseline, while our parallelization technique provides up to

35\times

improvement overall (on 8 cores).

Maxim Ivanov, Matvei Smirnov, Alisa Strazdina +1

Data Mining Profiling Conflict-Based Search Parallel Decoding and Training Utility Maximization Universal Factorization Problem+3

Ask PDF

Oct 1, 2025cs.LG

Panorama: Fast-Track Nearest Neighbors

Approximate Nearest-Neighbor Search (ANNS) pipelines for high-dimensional neural embeddings spend the bulk of their query time in candidate verification, making it the primary bottleneck in the search process. In this paper, we present PANORAMA, a state-of-the-art refinement technique that accelerates verification by exploiting the inherent spectral decay of these embeddings. Using PCA to compact signal energy, PANORAMA evaluates candidate distances incrementally, computing at each step a strict lower bound on the full-vector distance and dynamically pruning candidates the moment this bound exceeds the running k-th nearest neighbor distance. While PCA's concentration of variance facilitates pruning, it breaks the uniform-variance assumption required by Product Quantization (PQ); we resolve this with a variance-shaping step that redistributes energy across subvectors, rendering accretive refinement compatible with quantized indexes. Optimized for modern memory hierarchies via vectorized bulk-pruning and cache-conscious data layouts, PANORAMA has been upstreamed into the FAISS library across major index families (IVFPQ/Flat, HNSW, and Refine). PANORAMA achieves higher QPS at any target recall with a cost that provably scales inversely with dataset spectral decay, delivering end-to-end speedups of up to 28.9x and outperforming probabilistic methods across all recall bands.

Vansh Ramani, Alexis Schlomer, Akash Nayar +3

Approximate Nearest-Neighbor Search K-Nearest-Neighbor Neural Architecture Search Calibration-Free Low-Bit Vector Quantization Hyperspherical Embedding Geometry Principal Component Analysis+3

Ask PDF

Jun 23, 2026cs.AI

Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index

Spectral filtering recently delivered substantial pruning for \emph{static} subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query. We study whether such aggregate structural tests can accelerate \emph{continuous} subgraph matching (CSM) over dynamic graphs, and answer in three parts. First, lazily maintained spectral bounds are infeasible exactly where spectral pruning has value: we characterize the tightest safe rule over a formalized perturbation relaxation and show that even it loses essentially all pruning power within four touching updates. Second, exact maintenance is affordable when selective: pruning utility and recomputation cost are anti-correlated across vertices -- hubs provably never prune -- so recomputing small-neighborhood spectra on touch sustains exact local spectra at microseconds per update, complete by construction. Third, integrated into a decoupled CSM benchmark against an identical-minus-spectra control, the tests remove up to

51\%

of candidates or safely skip up to

47\%

of update enumerations, yet enumeration intermediates remain unchanged -- beyond the gates' skipped first-level bindings, typically zero -- across two engines, four real graphs, two stream types, and

77

solved queries; a constructed radius-stratified workload confirms the instrument detects the exception when one exists (

-99.9\%

intermediates,

748\times

faster). Aggregate tests accelerate what scales with candidate sets -- construction, list scans -- never adjacency-guided exploration. We distill an intermediate-invariance methodology for evaluating CSM filters and release a reusable dynamic local-spectra index.

Minghao Chen, Jiale Zheng

Subgraphs Graph Laplacians

Ask PDF