论文标题
矩阵配置文件xxii：确切发现时间序列图案DTW下的时间序列图案
Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW
论文作者
论文摘要
在过去的十年中，时间序列图案发现已成为许多下游分析任务的有用原始性，包括聚类，分类，规则发现，细分和摘要。同时，人们对动态时间扭曲（DTW）是在许多设置中的最佳时间序列相似性度量的越来越多。但是，令人惊讶的是，几乎没有使用DTW发现图案的工作。最明显的解释是一个事实，即基序发现和DTW的使用在计算上都具有挑战性，而当前解决其嗜睡的最佳机制是互不相容的。在这项工作中，我们提出了第一个可扩展的精确方法，以发现DTW下的时间序列图案。我们的方法会自动执行我们介绍的新型层次结构的较低层次结构之间的最佳权衡。我们表明，在现实的设置下，我们的算法可以降低多达99.99％的DTW计算。
Over the last decade, time series motif discovery has emerged as a useful primitive for many downstream analytical tasks, including clustering, classification, rule discovery, segmentation, and summarization. In parallel, there has been an increased understanding that Dynamic Time Warping (DTW) is the best time series similarity measure in a host of settings. Surprisingly however, there has been virtually no work on using DTW to discover motifs. The most obvious explanation of this is the fact that both motif discovery and the use of DTW can be computationally challenging, and the current best mechanisms to address their lethargy are mutually incompatible. In this work, we present the first scalable exact method to discover time series motifs under DTW. Our method automatically performs the best trade-off between time-to-compute and tightness-of-lower-bounds for a novel hierarchy of lower bounds representation we introduce. We show that under realistic settings, our algorithm can admissibly prune up to 99.99% of the DTW computations.
