arXiv:2607.17481cs.AIcs.DB2026-07

一次性流式计算所有窗口长度的模式发现,速度提升百倍以上。

Panache: One-Pass Motif Discovery at Every Window Length

  • 通过滑动DFT在线维护频谱状态,避免重复自连接计算
  • 在17个UCR数据集上找回全部前20个基准模式,准确率100%
  • 适用于需要高效探索时间序列模式的研究者或工业场景

模式发现是时间序列探索性分析的核心任务。由于模式持续时间未知,传统方法需遍历指定长度区间内所有可能长度,对每个长度执行一次z标准化矩阵轮廓计算,导致需进行L次二次自连接操作。本文提出Panache,据我们所知首个针对z标准化潘矩阵轮廓(PMP)模式发现的一次性流式算法。它将重复自连接替换为仅一次近线性复杂度的扫描。关键洞察在于:子序列均值中心化仅影响其直流傅里叶系数,其余非直流频谱可通过滑动DFT递推和运行统计在线维护。该频谱状态用于在受控哈希目录中碰撞相似子序列,并基于帕塞瓦尔定理生成下界,在精确计算前排除绝大多数不匹配对。Panache 自动计算所有数据依赖参数,仅需设置资源预算。默认预算下,其在17个UCR配置上完全复现了精确固定排除基准的前20个潘模式;在510万样本的Wafer数据集上,单次扫描仅耗时2.9分钟,完整输出精确模式用时6.0分钟,远超最快CPU基线(7.95小时)与H100 GPU上的SCAMP(38.3分钟)。

原文摘要 · Abstract (English)

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.

模式发现时间序列流式计算高效算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。