Searching and Mining Trillions o
0. 摘要
目前所有对时间序列数据进行分析的算法都是以相似度搜索为基本框架的，这样就导致目前所有的时间序列挖掘算法都是以相似度搜索为瓶颈。这就导致所有的时间序列挖掘算法能处理的数据量都在百万这个量级，但是实际上工业界和科研的需求都已经达到了十亿这个级别。本论文首创在更大量级上进行数据挖掘的方法。这个有点违反直觉，但是使用dtw进行大数据搜索，比目前最前沿的技术：欧氏距离搜索算法更有效率。我们论文所基于的实验使用的数据量超过了以往所有同类论文的总和（那可不，以往的论文数据量在百万，即使以前有一万篇相似论文，数据总量加起来也才百亿而已，当然远不如万亿这个量级，这有点找角度吓唬人的感觉），这表明dtw这个方法很棒，可以用于解决更高级的时序挖掘问题，如motif 发现，大数据聚类。除了用于处理大数据之外，该方法还可以用于实时监控数据流，还可以更高效的处理数据，降低对设备的需求。
1. 引言
传统的DTW算法应用于众多领域：机器人、医药、生物测量、音乐/演讲处理、大气、航空、手势识别、交互界面、历史手稿挖掘、地理、天文学、太空探索、野生动物监控。以往使用dtw做的研究肯定挺多的，但是都会认为这个方法计算代价太高，不实用。但是实际上经过我们的UCR四件套的改造，可以使计算效率得到极大的提高，不过这UCR四件套挺难证明的。改造后的DTW算法快目前所有的近似搜索和索引搜索算法。作者还举了几个例子。
文献28中说：长度为1000的查询，用dtw可以获得95% 的准确率，在百万数据集上用随机游走的方式，耗时5.65秒。而本文的dtw只需要3.8秒（同数据集、同配置的机器）。
另一篇基于內积来求dtw下界的方法，进行“文本中新词发现”任务的研究，作者声称用dtw-knn方法大概需要2分钟。而用我们的方法，只需要不到1秒。
另一篇比较出名的多点触屏的手势识别领域的论文中说：dtw需要花费128.26分钟来对160个手势进行14400个测试。而用我们的方法，只需要3秒。
1.1 万亿量级问题简述
整整一段的吹牛，不翻译了。
1.2 问题假设
A 时间序列必须是正则化的
同样的方法，处理非正则化的数据和正则化数据，两者正确率的区别很大（50%和5% 的区别）
B DTW是最好的测量方式
在其他论文中早有声明：dtw是最好的方法，只是因为效率太低。
C 任意长度的查询是不能被索引化的
D 有些数据挖掘问题的还是值得我们等个几小时的。
6. 总结
一大段的吹牛，说自己的UCR-DTW算法效率高。还跟最近的state of art EBSM作对比。说自己需要的准备工作少，适用范围广，计算速度快。
又“谦虚”的说近似搜索算法的发展空间很大，未来可能追上自己的研究，但是又委婉的指出自己目前的上限已经很高了，想追上也不容易呢。
然后说自己的研究比目前的各种的state of art都要快N倍（N取决于数据集和查询条件），然后证明了2个问题：
1. 认为DTW不行的悲观论者可以歇歇了（因为本论文提出了非常NB的UCR-DTW算法，在下界相关的技术上，DTW可以用于挺多问题的）
2. 再就是UCR-DTW和UCR-欧氏距离比当前的state of art快很多。
然后又惋惜的说限于篇幅不能贴完整的伪代码了，请移步43这个文献，观看下集（对！就是一项研究骗两个论文！）。
5. 实验结果
为了保证论文可复现，作者做了以下工作：
1. 原始问题：所有子序列都z正则化，使用欧氏距离进行dtw计算
2. sota：所有子序列z正则化，使用提前终止技术，使用lb_keogh做dtw下界。
3. UCR套件：用了所有可能的加速技巧。像dtw的r=5%拉 ，能用递归就不用遍历拉。保证大家的对比绝不是因为这些小的细节，而是因为根本的设计思想不同。
5.1 随机游走的基线
image.png
可以看到，长度为128的查询中，UCR改造过的方法，运行速度比sota快多了。尤其是sota-dtw和ucr-dtw的对比，impressive呢！
image.png
对于dtw的三个变种，可以看到，越长的查询，三者差距越明显。
跟goal相比，ucr所花时间/goal说话的时间 = 1.41。这暗示着我们的算法已经非常接近极限了，可能不存在继续优化的空间了。
再就是ucr-ed和ucr-dtw相差很少，只差1.18倍（？这是咋计算出来的？），这跟近年来的研究并不一致。
5.2 长查询：EEG（脑电图）
image.png
这是俩医生收集的脑电图数据，然后用两种算法去算，看看时间
image.png
可以看到，对比很明显。
后面就不看了，反正就是效果不错。
3. 背景与声明
3.1 定义
1. 时间序列T是一个有序的列表，T= t1，t2，t3…..因为原始数据的长度会很长，所以我们总是用其子序列去进行比对。
2. Tik代表从i数长度为k的子序列。Tik可能用C来表示，说这是一个Candidate的意思。Q表示查询。|Q| 记为n（查询的长度为n）
3. 当|Q| =|C|, 时，Q和C之间的ED距离定义如下：
image.png
如下图所示：
image.png
ED是两段序列的一一映射距离，可以视作dtw的一个特例。当使用dtw来对齐两个序列时，需要先构建n·n的矩阵。
image.png
表示qi和cj之间的距离。
P就是一个规整之后的轨迹。p的第t个元素记为pt=（i,j）t，所以P表示为：
image.png
同时P有一些约束，必须是对角线，必须是相邻点连接，并且p上的点必须是单调的（只能递增，不能先增后减）。还定义了可以偏离对角线的程度，一个典型的约束就是Sakoe-Chiba Band，表明不能偏离R的宽度。
image.png
4. 算法
4.1 已知的各种优化
4.1.1 使用平方距离
因为平方和距离MSE 和平方和再开方距离 RMSE相对大小是一致的。都是单调的凸函数，而且mse更容易优化。
4.1.2 下确界
DTW这类计算代价较高的算法，常用的优化手段就是通过寻找下确界来进行“剪枝”（减少待选的计算量）。下图就是两种简化计算的例子，其中一种是本文采用的。
image.png
4.1.3 early abandon（ED和LB_keogh）
如果已经计算得到的欧氏距离或者LB_keogh下界超过了best-so-far，那就停止计算，因为这肯定不是最优的路径距离了。
image.png
4.1.4 DTW的early abandon
当计算LB_Keogh的时候，有时必须得先全量计算欧氏距离，但是仍有一个小技巧来提高计算速度。我们可以从左到右增量计算DTW，当我们计算1k时，我们可以计算部分的（从k+1n）DTW的LB_Keogh累加和。
image.png
这个累加和是真正的DTW距离的一个下界。这个是可以推导出来的。如果这个和超过了best-so-far，就可以进行剪枝。
4.1.5 并行计算
多核并行可以线性的提高计算速度，下一节就是讲多线程的。
4.2 新优化：UCR套件
基础这些工作，我们还做了以下原创性的工作。
4.2.1 z正则化的early abandon
据我们了解，还没人试过在正则化上进行优化。这让人有点意外，因为这个过程所花的时间比计算欧式距离还要久。
我们对z正则化的过程进行了early abandon，就是我们在增量计算z正则化时，也增量计算了欧氏距离（或者LB_Keogh距离），如果我们进行了剪枝，那么同时也就减去了很多z正则化的计算。
均值和方差的计算可以通过一次遍历得到，计算公式如下：
image.png
在相似度搜索中，所有的子序列在与查询进行比对前需要先正则化。子序列的均值可以通过维持两个累加和，两个累加和之间有m个点的延迟。平方和的累加也可以用类似的方式得到，公式如下：
image.png
更高水平的算法伪代码如下：
image.png
其中第11行允许在正则化这个步骤进行剪枝。在这个算法中，用循环遍历X来存储当前子序列与查询Q的相似度。
4.2.2 重排序的early abandon
经过测试，根据每个点对欧式距离的贡献，对Ci进行由大到小的排序，按这个顺序进行计算，可以加快速度，这是个基于经验的优化，用心跳的那份实验数据证明过。
4.2.3 在LB_Keogh计算中，反转查询和数据的角色
在4.1.2的举例中，在查询上做了一个envelope，一个我们用来讨论LB_KeoghEQ的情况。这个步骤只需要做一次，可以节省额外的开销。
image.png
当所有的剪枝手段都失效时，我们可以用实时计算的方式选择性的计算LB_KeoghEC。考虑到LB_KeoghEQ ≠ LB_KeoghEC，平均来说每个都多花费了一半以上的时间。所以这种尝试是很值得的。
4.2.4 流式计算的剪枝
image.png
通过比较所有剪枝方式的tightness和时间复杂度，我们得到一个结论，那就是看情况在流式计算中应用所有的剪枝手段。
