DTW算法挖掘亿万级时序数据，其优化能耐几何？

等长数据，比如：比较近10天两只开盘股票走势k线图
不等长数据，比如：相同时间内不同抽样频率（Hz）的心电图、两段“麻烦请开门”的语音音频

因此，日本学者Itakura最早提出 Dynamic Time Warping（下文简称DTW，中文常翻译为“动态时间规整”）算法，它出现的目的也比较单纯，是一种衡量两个长度不同的时间序列的相似度的方法——在对齐两个序列的过程中通过定义的距离计算公式计算序列的相似度。其应用广泛，主要在于模版匹配，如孤立词语音识别、手势识别、DNA序列配对等。

这里，距离计算公式包括（但不限于）上文提到的欧式距离。

允许在对齐过程中，有些点被跳过，没有被对齐——取决于定义的“步”。
由于矩阵中路径上的每个点都能分解为一个“多点到达”的子问题结构，因此dtw就是通过动态规划法（dp，dynamic programming）进行求解的一个例子。

在后面给出的DTW算法的python简单实现中，通过在循环中约束i和j的关系实现global constraint——通过简单画图可以了解。

那简单介绍完DTW的原理之后便引入了这篇论文《KDD2012 Best Paper-"Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping”》[1]。

上文提到，DTW在多个领域都有所应用。随着互联网的到来和数据量的爆发（很多生产环境数据量早已突破万亿级别，而学术界仍停留在百万、十亿级数据集的研究上），原始DTW的实现弊病暴露，场景的应用对算法的性能提出了更高的要求，而该论文的核心正是通过对其他论文的review，现有优化方式的review以及对提出的计算优化方案的review来告诉我们，优化后的DTW（论文称为UCR suite）仍然是最强最快的时序相似度计算方式。

论文首先指出以下假设或事实：

lower bound具体计算方法有多种，如稳重提到的LB_kim，LB_keogh。

We conjecture that the universal optimal ordering is to sort the indices based on the absolute values of the Z-normalized Q.
For this we simply take each Ci and sort them, largest first, by their sum of their contributions to the Euclidean distance.
We compared this empirically optimal ordering with our predicted ordering (sorting the indices on the absolute values of Q) and found the rank correlation is 0.999.