摘要
动机发现是探索性数据分析中的核心原语，旨在寻找时间序列中的重复模式。然而，模式的持续时间通常未知。为了解决这个未知的持续时间，定义了一个窗口长度的区间，现有方法需要在该区间内尝试每一个长度。现有的平面矩阵剖面（PMP）方法为每个长度计算一个z标准化的矩阵剖面，因此对于$L$个长度，需要进行$L$次二次自连接操作。
我们提出了Panache，至今为止首个用于z标准化PMP动机发现的一次性流式算法。它用单次扫描替代了重复的自连接，其运行时间接近线性，依赖于序列长度。关键观察是，子序列的均值居中仅改变其直流傅里叶系数，因此每个z标准化子序列的非直流频谱可以通过滑动DFT（离散傅里叶变换）递归和运行统计在线维护。这个频谱状态是相似子序列在一个占用控制哈希目录中碰撞的关键，并通过Parseval定理，提供一个下界以在任何精确计算之前拒绝大多数碰撞对。
Panache能够自动计算每一个数据依赖的参数，仅留下资源预算以供调优。在默认预算下，它在17个UCR配置中恢复了所有前20个平面动机，且在速度上超越了本文中基准测试的每一个CPU和GPU基线。在对Wafer进行五百万个样本和51个长度的测试中，Panache在2.9分钟内完成一次扫描，并在6.0分钟内输出精确动机，而最快的精确CPU基线耗时7.95小时，SCAMP在H100 GPU上耗时38.3分钟。
博主点评： Panache算法的设计理念突破了传统的多次自连接方法，通过一次性流式处理显著提高了动机发现的效率，展示了数据处理领域的创新思维。其在资源使用和运行时间上的优势为大规模时间序列分析提供了新的解决方案，值得广泛关注与应用。