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.

本文介绍了一种可扩展的准确方法，用于使用动态时间扭曲 (DTW) 发现时间序列 Motifs，该方法可以在时间和较低下限的紧密度之间自动执行最佳权衡，并且在现实设置下，该算法可以删除多达 99.99％的 DTW 计算。