标题：ParIS：快速时间序列索引和查询应答的下一个目标

本文与2018TKDE-ParIS+: Data Series Indexing on Multi-Core Architectures几乎是同一篇，一篇在会议，一篇在期刊，期刊文章做了些补充说明和优化，合并在一起说了。

编者的总结：

1. 本文为iSAX提供了一种并行化算法，非常细粒度的并行，基于少量性能强劲的服务器，将similarity search的建索引和精确查询效率提升了一两个数量级，是非常卓越的进步。
2. 本文没有基于任何计算框架或者分布式服务，直接自己操控磁盘读写和内存控制，对于精确查询，选择了分区全盘扫描一遍SAX，利用原子操作BSF控制剪枝，最终也达到了了非常好的效果。

编者的思考：

1. 本文只考虑了非物化的情况（基于ADS），没有考虑物化时的加速。
2. 磁盘读写的并行性没有考虑，尤其是在多个硬盘上。
3. 精确查找时，没有对iSAX的树结构加以利用，重复计算了很多无效下界距离。
4. 近似查询的召回率和精确率，文中没有太多展示。

ABSTRACT

第一款基于磁盘的数据序列索引，利用了现代硬件的并行性。
实验表明对于基于硬盘的数据，在索引构建过程中，Paris完全移除了CPU延迟（全部取决于IO）。
对于精确查找，是index方法的2个量级的提升，serial scan 3个量级的提升。
主要是源于多核+multi-socket的利用，另外一方面每个核又用了SIMD，使得索引构建和查询应答都得到了很大提升。

I. INTRODUCTION

作者评估了执行速度和线程间通信之间的tradeoff，最后发现对于不同的硬件有不同的方案，让各个worker thread之间达到一个平衡以交换信息。
实验基于单个机器，用来最大化硬件的性能。但是也可以扩展到集群机器上去。
作者还基于SIMD做了一个向量式的iSAX下界距离。

II. PRELIMINARIES

image.png

ADS+是本文local所用的index tree，主要特征是第一层有至多个节点，但是下层是二叉分裂的。

III. PROPOSED SOLUTION: PARIS

A. ParIS Index Building

因为I/O是主要的时间损耗，所以作者提出，构建索引时要尽量完成两个目标：

1. 让CPU时间尽量和I/O时间overlap起来
2. 尽可能减少磁盘的随机I/O

为了达到这两个目标，就要尽量减少各线程间的同步通信。

image.png

Stage1：coordinator worker从磁盘中读数据，读到的数据放进Raw Data Buffer。
Stage2：一组IndexBulkLoading Workers从Raw Data Buffer里面分区读数据，转换成iSAX形式，存入RecBufs和SAX数组。
Stage3：一组IndexConstruction从RecBufs中读取数据，构建iSAX Tree(ADS+ tree)，建好之后，把叶子节点的数据flush到磁盘中。

Raw Data Buffer由两个数组buffer构成，corrdinator读满了B1，则启动一组IndexBulkLoading workers去处理B1，同时corrdinator向B2中读取数据。因此读取(I/O)和iSAX转换处理(CPU)可以同时进行，而负载的I/O可以mask out 掉CPU处理的时间。
Reciving Buffers就是ADS+树的第一层节点，每个节点一个buffer。

image.png

这三个阶段，不是严格的step-by-step的，raw data buffer读完了就会启动bulkloading过程；另外coordinator会记录当前读过的time series，一旦内存满了（到达一定界限），启动construction workers，分配RecBufs，flush掉当前内存里的time series。

indexbulkloading worker的个数通常是CPU核数-1，留下一个给cordinator。index-construction worker一般是CPU核数，此时coordinator也停止了读取工作。实际使用中5-6个worker已经足够让CPU的延迟被I/O mask out掉了。

在bulkloading的过程中，各个worker从raw data buffer不同的偏移量开始读取处理，这样就避免了同步。唯一需要同步的就是对RecBufs的锁，然而由于RecBufs有至多个，一般是几百到几千，workers最多也就几十个，所以锁的使用可以忽略不计了。

raw data buffer在作者的实验环境中用的是2MB，实验显示时延一开始递减，2MB之后开始趋于平稳，可以想到再大CPU也处理不过来了。

最后是index-construction过程，如下图，这个过程为每个local index的叶子节点，都分配了一个Output buffer。这个Output buffers收集叶子节点中的time series数据和iSAX表示。

image.png

每个worker依次去取一个RecBuf来处理，在Worker内部没有进行并行化。注意到由于time series是one-by-one插入的，所以叶子节点会经常分裂，此时要读取OutBufs，然后再分裂OutBufs。

• Paris+：由于在这个过程中，index-construction workers的工作的一部分，就是构造iSAX树，这一块是CPU操作，然而没有被I/O mask掉。在Paris+中，可以让index-bulkloading worker兼容这部分工作，index-construction workers只负责flush OutBufs，使得CPU操作全部被mask掉。

• 总结：无论是Paris还是Paris+，实际上构建的都是一个非物化的索引，不改变原数据的组织，也没有涉及到数据的物化。

B. ParIS Query-Answering

exact query的方式是首先进行approximate query，确定好一个BSF，然后再扫描全部序列。
近似query大部分都是内存操作,扫iSAX Tree到叶子节点即可。

扫描全部序列包含两部分，一部分是利用每个序列的iSAX，算下界距离；另一部分是合格的candidate算真实距离。

3.3.1 lower bound distance calculation

由于下界距离的计算本质上是一个向量计算（每个PAA做向量的一个元素），如下图，那么就可以使用SIMD的指令。然而下界距离有3种Case需要判断，根据不同的Case有不同的距离计算公式，SIMD不支持条件分支指令，因此作者的方案是，三种case全都算一遍。然后再单独产生3条mask串，定位每个PAA应该采取哪个case，每个结果都和mask做下AND，最后结果再or起来，就产生了最终的距离计算结果。
根据作者的实验，排除I/O的影响，SIMD也会比SISD快2.6倍。

image.png

3.3.2 Exact Search in nb-ParIS+

多线程对SAX表分块，每个线程计算下界，满足条件的取数据，计算真实距离。只计算local BSF，各个线程不通信。和ADS+(sims）非常相似。

3.3.3 Exact Search in ParIS+

对于粗粒度的并行化，作者将之前整理好的SAX向量，分块，分给LBC(Lower bound calculation worker)进行计算，各个块之间也没有同步需求。
对于下界符合要求的进入candidate list，所有块完成之后，达成同步。
此后启动数量更多的RDC(real distance worker)，由于IO操作更密集，因此数量要更多。这些RDC原子化的读取candidate，计算真实距离，原子化的更新BSF，最终得到结果。
作者从实验中得到结论，LBC每核一个，RDC每核5个左右，可以达到较好效果。

image.png

3.3.4 Discussion of nb-ParIS+ and ParIS+

1. nb-Paris+在各个块之间的任务分配是不均衡的，因为剪枝率不是均匀分布的；
2. nb-Paris+实际上造成了磁盘的随机访问；
3. Paris+的同步操作要远远比nb-Paris+要高。

IV. EXPERIMENTAL EVALUATION

两台服务器，每台服务器两个处理器，每个处理器12核，75GB内存。
这个实验环境有些复古，单机有非常顶级的服务器配置，有足够大的内存

4.1 Results

4.1.1 Index Creation Performance Evaluation

首先是索引构建时间，用的数据集是合成的，100M个序列，110GB大小。整体来说和ADS+在一个量级上，少1倍时间左右。
比较值得关注的是Fig.6，构建时间图。可以看到IndexBulkLoading Workers在6核及以上的时候，可以完全被raw data read cover掉，当然这是由于实验环境内存足够大的时候。
另外，虽然indexConstruction workers可以很快构建iSAX Tree,但是把OutBufs flush到磁盘里，还是占据了大量的时间。

image.png

image.png

4.1.2 Query Answering Performance Evaluation

PARIS多核并发读SAX分区，单核内SIMD用于下界距离计算，SIMD也可以用于精确距离计算。
图中的ADS+应该不是ADS+(SIMS)。

• 从实验结论看出，均衡的线程间工作分配，和较为连续的磁盘读，使得Paris+性能很不错。

  
  
  

  image.png

• 这个过程因为有大量的随机读取，所以SSD比HDD快了很多，实验没有给出精确数据，从图中看，在SSD上，250GB仅有几秒的响应，已经是史无前例的了。

  
  
  

  image.png

VI. CONCLUSIONS

作者提到，future work可以有三个部分：

1. 深度的IO并行；
2. 将本方法和已有的分布式系统技术结合起来；
3. 其他距离计算：DTW。