编者的总结

本文做的是并行whole-matching，可以处理近似搜索（效果基本等同iSAX），也可以处理精确查找。主要场景是内存数据，几百GB是实验最大的数据量了。精确查找是目前所有方法中最佳的，100GB仅需几十ms，基本可以支持线上查询了。
主要的idea就是在充分利用剪枝信息的情况下减少同步，一方面利用树形结构的下界特性形成了大规模的叶子剪枝，又利用优先级队列和对BSF的锁再次进行剪枝，极大地减少了下界计算（相比于PARIS）。

编者的思考

对于并行化技术，编者认为此文做到的已经基本是极限了，对PARIS的不足有很多改进。
然而scalability仍然是问题，基于强劲的少数服务器，手动实现的并行框架，仍然有很多瓶颈问题，尤其是I/O方面，这意味着不能与现有的分布式环境做兼容。现有的框架如Hadoop,spark,presto等无法直接应用。

Abstract

本文的目标是实现交互式时间序列分析，手段是在现代硬件上（SIMD，多核）实行内存操作，优化主要来源于多个worker之间的高效合作和数据结构的设计。
实验结果显示，100GB上精确查找，只需50ms左右。

I. INTRODUCTION

作者充分平衡了多个worker之间的协作沟通和单个Worker的效率。用并发的优先级队列来存储未能剪枝掉的时间序列。基于index tree来决定什么序列可以进入队列。workers随机选择一些队列来处理。

III. THE MESSI SOLUTION

image.png
本文的算法基本可以由这张图来看，假设row data存储于内存中，并预先分割成若干chunks。索引构建过程并行启动

N_w

个index worker线程，各线程用FETCH_AND_INT的方法消费各个chunk，为每个time series计算iSAX，算出来之后，立即就知道了这个iSAX应该属于哪个root subtree的，我们预先为每个root subtree构建一个buffer，至多

2^w

个，

w

是segment的个数。index worker要把每个time series的iSAX放到正确的buffer里，因为不同的worker可能会写入同一个buffer，所以在一个buffer内部，再分成

N^w

个小buffer，这样就避免了同步。

image.png

这里产生一次同步，等到所有worker工作完成，iSAX buffer写好。然后进行下一步，index worker同样使用FETCH_AND_INT方法消费一个buffer，对buffer内的所有小buffer进行isax tree的构建。

image.png

之后进行第二次同步，所有worker工作结束，iSAX tree index也就构建完成了。

接下来讲exact query的过程。exact query 首先由一次近似query开始，这次近似query是集中式操作，沿着iSAX树找到叶子节点，统一算下距离，得到BSF。注意，这个BSF的维护，将来会是全局的，基于锁，因此算法结束之时，BSF就是最终结果。

image.png

之后我们启动一组search workers，再预置一组priority queues。每个search worker随机分配一个queue，然后依然用FETCH_AND_INT的方式，消费每一个root subtree。search worker递归地遍历这个root subtree的每一个节点，如果下界条件不满足，连根砍掉，否则继续递归；对于满足下界条件的叶子节点，将其置入分配的queue，然后queue++，以满足round rubin。由于每个queue可能同时被分配给多个search worker，因此要配置锁。

image.png
注意到priority queues的个数是用户指定的一个固定值。作者基于这个问题做了实验：固定值最少是1，那么同步开销过大；固定值最多是线程数，这又导致了工作过度不均衡，折中一下，才能获得最好的效果。

队列写入这里需要做exact query的第一次同步，要求队列全部写好再开始下一步，已保证队列的负载均衡。接下来search workers再次用FETCH_AND_INT的方法依次消费所有queue。如果出队的节点下界条件不满足，则整队砍掉。否则依次计算节点下界，time series下界，最后才算真实距离，然后不断更新BSF。

image.png

注意到，本文设计的所有距离计算，下界计算，都可以通过单核的SIMD来进行加速。

IV. EXPERIMENTAL EVALUATION

实验环境毫不意外，又是两个超级服务器。每个都是双处理器，每个12核24线程256GB内存，C语言实现。
对比的方法是PARIS,PARIS-TS(PARIS的一个升级版)，UCR-P（并行版UCR，并行计算，只在最后进行同步）。
数据集有合成数据集（50GB-200GB），真实数据集（100GB），长度256.

B. Parameter Tuning Evaluation

首先是parameter影响的一个探究。

chunk size设置稍大一些，构建时间和PARIS相差不大，100GB在20s以内。

image.png
叶子容量越大，构建越快，这是显然的，不过到5K以后也基本收敛了。叶子较小，index tree太高，查询较慢；叶子太大，剪枝太少，更容易导致search workers之间负载不均衡，查询较慢；居中较好，2K-5K皆可。

image.png
对于iSAX buffer size，也是不可忽视的一部分，因为量太大了，实验做下来发现其实buffer越小越好。作者也试过完全不用buffer，但是不行，太慢了。

image.png
在多核情况下(24以上)，多队列比单队列要高效。第二张图更加明显，单队列的情况下，各线程在抢队列，几乎40%的时间花在了同步上。

image.png
image.png
过于多的队列，其实也没什么用。

image.png

C. Comparison to Competitors

相比于PARIS，MESSI建索引时间更短，主要是因为写入iSAX buffer时没有同步，以及读chunk的负载更加均衡。另外，二者的性能增长，随着核心增加逐渐变慢了，这是由于同步。

image.png
相比于PARIS，MESSI的可扩展性更好。

image.png
相比于PARIS，MESSI query answering time 提升了0.5-1个数量级。

image.png
image.png
作者表示，他提供的这种并行技术，只在root subtree有很多时候才适用，对于二叉树(DS-Tree)，要有新的设计才行。但是SIMD，优先级队列，是大家都可以适用的。如下图，针对PARIS而言，SIMD相比于SISD提升了60%。而index tree的并行遍历又使得PARIS-TS能够大幅度削减搜索空间，减少大量的下界计算，使得性能再提升10%。而MESSI，通过只入队合适的leaf node，大幅度削减了队列的size；而且通过多队列，减少了通信开销，使得性能再提升83%。

image.png
MESSI大幅度削减了下界的计算，由于队列里是叶子节点，之后未必会进行真实距离计算，所以真实距离计算也会减少，但是减少的幅度不稳定。

image.png
DTW距离一样可以加速，用 $LB_{Kough}$ 代替iSAX即可，索引结构不变。

image.png