标题：在DTW距离下，搜索和挖掘万亿个时间序列的子序列

编者的总结：

1. 本文的贡献其实主要在于一些编程技法的提升，cascading的利用了各种LB，这么多LB在单次距离计算上未必有用，甚至可能浪费时间，但是需要做G甚至是T数量级的距离计算时，提供了大量的剪枝，避免了O(nR)的完整DTW运算，大量计算在O(n)层面被剪枝，导致性能有成量级的提升。这是一个非常通用的方法，不仅是similarity search，在大量需要距离计算的位置，都有显著的作用，从这点上来说，意义是很大的。

编者的思考：

1. 本文在介绍时说，non-normalized的距离衡量没有意义，这一点再2019KV-match有反驳，意义还要再考量；
2. 本文在介绍时还说，任意长度的查询索引不会存在，这里也过于武断了，2018ULISSE（有限范围内），2019KV-MATCH（不限制范围的-search），都有任意长度的味道。未来对于任意长度的similarity search，也许还可以基于长序列的特征挖掘，多序列之间的关系挖掘来构建索引，未必不能实现；
3. 本文的实验部分还提到了real-time的部分，十几分钟的耗时说是比256Hz的采样频率快，这里还不是很理解，是否足够支持实时，也有待考量。

ABSTRACT

作者研究的量大，达到TB级别；而且速度快，结合了四种新思想，使得在DTW下的Query速度甚至超过了ED下的近似速度。而且似乎还可以做real-time monitor了。

1. INTRODUCTION

讲了两个意义，一个是DTW的广泛应用，一个是大量的时间序列。
DTW的主要问题在于太慢，作者用本文方法复现了很多之前论文的实验，速度惊人，都在秒级别。

1.1 A Brief Discussion of a Trillion

描述一下数据量之大。

1.2 Explicit Statement of our Assumptions

1.2.1 Time Series Subsequences must be Normalized

作者提到如果去比较两个时间序列，两个必须都要normalized，否则没有意义，直接去normalize整个数据集也不可以。
同时还批驳了两个论文，认为他们没有提供normalized的方法，所以意义不大。
（编者注：normalize是否是必须的，还需探讨；normalize的过程也会对原始数据的信息造成缺失，un-normalized也未必就没意义，2019KV-match的论文中对此有过举例）

1.2.2 Dynamic Time Warping is the Best Measure

ED作为DTW的一种特殊情况，作者经过大量的比较，发现DTW是最好的衡量方法。

1.2.3 Arbitrary Query Lengths cannot be Indexed

现有的方法预知长度范围，建立多个索引，空间占用太大了不可行。
如果某个索引基于某种长度建立，如果以其它长度query，由于之前所说的normalized的问题，索引就失效了，因此得出结论，可变长度的查询不能被索引。
（编者注：这是基于索引是定长的来考虑的，如果索引本身就支持变长的，那么也未必不可索引，参考2018ULISSE，2019KV-MATCH）

2. RELATED WORK

3. BACKGROUND AND NOTATIONS

ED DTW DTW-R对角线限制等。

4. ALGORITHMS

4.1 Known Optimizations

4.1.1 Using the Squared Distance

ED/DTW的平方根先不开，正常计算，最后返回结果时候再开平方根

4.1.2 Lower Bounding

先找到一个距离下界，然后用以剪枝。

4.1.3 Early Abandoning of ED and

计算LB的时候，如果LB都超过了BSF的距离，就可以early abadoning。

4.1.4 Early Abandoning of DTW

是说LB算完了明确小于BSF，就要计算真实的DTW，DTW是递进式计算，可以在计算到第K步时候，把前K步的真实DTW距离，和后面n-K步的LB加起来，变成一个更紧的LB，与BSF比较，用于剪枝，

4.1.5 Exploiting Multicores

本来DTW是能够通过多核进行线性优化的。但是本文的UCR Suite并行度没那么高，但是效果远比之前多核的要好，多核的问题，后面会讨论。

4.2 Novel Optimizations: The UCR Suite

4.2.1 Early Abandoning Z-Normalization

作者说，尽管Z-normalization耗时比ED的计算还要略高，但是没人对这个过程进行优化。可以通过running sum的方式对Z-normalization进行incremental式的计算，而且这个过程还可以和ED/DTW距离计算放在一起。

image.png

作者提供的算法用一个环形的buffer来迭代计算Z-normalization，中间ED/DTW的计算还可以做Early Abondon。
还有一个问题就是Z-normalization那里浮点加减容易累积error，作者提供的方法是1M次重新彻底算一次。

4.2.2 Reordering Early Abandoning

两个子序列算ED/DTW的时候，一般是从左到右顺序算就好了。然而，为了适应Early abondon，越早算两点距离越大的越好，就是要确定一个计算的顺序。作者是这样考虑的，Query的母序列S，由于normalize过了，是均值为0的高斯分布，从概率上讲，Q离0越远，越有可能贡献大的ED距离。所以就按Q的绝对值大小排序计算。
作者也和理论optimal的顺序对比了一下，两种order非常接近。

4.2.3 Reversing the Query/Data Role in

刚引进下界的概念，我们可以对Query做下界，好处是只需做一次。相比于对于给DATA做LB，无需那么多次计算。仅在对于Query的下界无法做prune的时候，才对DATA做一次。

4.2.4 Cascading Lower Bounds

对于DTW的各种下界，作者做了实验，做了一幅图。基本上来说，复杂度越高，界限越紧。

image.png

作者的思想，就是把现有的这些LB，全都用起来，每一个LB，都和BSF去比较，具体来描述就是：

1. 首先把O(1)的LB算出来和BSF比较，如果prune不掉的话，下一步；
2. 递进的方式算，可以随时early abondon，可以用4.2.2的策略，如果prune不掉的话，下一步；
3. 接着算，同样，如果prune不掉，下一步；
4. 最后就是Early Abondon的DTW距离计算，用4.1.4的策略，最差情况下，即完整计算，最终可以更新BSF。

5. EXPERIMENTAL RESULTS

5.1 Baseline Tests on Random Walk

image.png

在不同长度的数据上，执行长度为128的similarity search耗时结果统计。

image.png

在不同长度的查询上，20M长的数据序列，耗时结果统计。
值得补充的是，作者说UCR-DTW是UCR-ED耗时的1.18倍，这个比例并不高。

image.png
上图是用于心电监测中的一个例子，G级别的数据，7000级别的查询序列，已经需要几个小时了。
还做了一个基因组测序的例子，长度2,900,629,179，2G长的数据，72500长的查询序列，耗时14.6小时。
作者还提到一个优化的方法，对于目前很多过度采样的数据，可以先降采样data和query，然后利用降级序列至少先提供一个LB作为BSF，之后prune效率会高很多。作者用这个方法做了一次，提升了不少效率。
image.png

8,518,554,188，8G长的数据，长度421的Query，是分钟级别的了。

作者还对现有的TS数据挖掘算法重新进行了优化，效果不错。