标题：超过10亿条时间序列：用iSAX2+索引和挖掘超大时序数据集
本文是2010年的ICDM论文：iSAX 2.0: Indexing and Mining One Billion Time Series的扩展版，内容全覆盖。

编者的总结

1. 虽然iSAX2.0+算法在当前（2021年）效率已经不能看了，但是这篇文章的算法设计和实验部分还是很赞的，尤其是减少IO的思路，同时大幅减少随机IO比重，以及在实验中单独体现这种understanding，都是值得学习的。

Abstract

本文的主要目的是降低索引构建时长，设计bulk-loading构建算法。

1 Introduction

3 The iSAX 2.0 index

3.1 Bulk loading: main algorithm

相比于iSAX的二叉树，iSAX2.0的构建作了以下变更：

• 第一层统一做个节点，根据SAX各段的第一位来分节点；
• 设置两个buffer组，FBL(First buffer layer)只缓存第一层的节点数据，每个节点对应一个buffer；LBL(Leaf Buffer Layer)只缓存叶子节点数据。

构建时，读入每一条原始数据：

• 首先尽可能地将数据根据SAX第一位填充到FBL，内存快要慢的时候，进入第二阶段；
• 遍历每个第一层节点（FBL中的buffer），开始构建iSAX子树，即定位到对应的叶子节点，如果叶子节点满了，需要从磁盘中读出该叶子节点中的序列，根据分裂策略进行分裂，生成两个新的leaf buffer进入LBL。

• FBL中的buffer遍历完之后，FBL也就空了，接下来要将LBL中所有buffer（叶子节点）中的序列flush到磁盘中。

  
  image.png
• 作者在这里提了一个问题：就是每一轮flush时，那些比较空的LBL中的buffer可不可以先不flush,因为太少了，能不能再攒一攒，等到叶子节点丰满一些再flush？
  • 答案是不可以，这样做性能并没有得到提升。因为其影响了FBL的写入量，导致了更频繁的刷新，实验中有做到。

3.2 Node splitting policy

iSAX在节点分裂时，选择哪一段的下一位开始分裂是采用round rubin策略的，那么分割很容易不均匀。iSAX2.0对节点分割策略做了一个改进，如下图所示。

• 对每一个分段的PAA求均值和方差，看是否cross下一位的split line，分割不过线那么大概率分割也是没意义的，是很不均衡的。
• 算法应尽量选择分割过线的段，如果都跨线了，就比较谁的均值离线更近一些。

• 注意到，这种算法基本是基于数据是正态分布的。因为数据是z-norm的，所以效果应该差不多。

  
  image.png

4 Efficient handling of raw time series data

本节首先提出非物化的思想。也就是SAX表示足够用来生成iSAX索引树，不需要原始序列来回从磁盘中读写。
但注意，虽然构建时不需要原始序列，构建完成之后，还是需要将原始序列放到叶子节点对应的文件里面去，以保证查询速度。

4.1 The iSAX 2.0 clustered index

iSAX 2.0 cluster对iSAX2.0的构建做了一些提升。首先从数据源读入FBL还是一样的，但是进入第二阶段时，算法直接将FBL中的buffer存的row time series写入文件，每个buffer（第一层节点）对应一个文件，称为FBL cluster，然后利用SAX表示来构建iSAX树。

在数据源读完一遍之后，iSAX树就已经建成了，之后算法依次遍历FBL cluster，对每一条序列找到其对应的叶子节点，再次利用LBL，待LBL满了，就flush其中的叶子节点到磁盘。

image.png

4.2 The iSax2+ index

isax2.0 cluster仍然对源数据集有诸多次I/O：

• 首次从数据源读取；（不可避免）
• 写入FBL clusters；（部分避免）
• 从FBL clusters读出；（部分避免）
• 写入正确的leaf node file里。（不可避免）

现在我们继续对这些IO进行优化避免。

• 基于的一个observation是，iSAX2.0树是较快就定型的，后面很少有分裂的情况。
  • 作者的一个实验，10亿条数据，当插入5亿条数据之后，树形状基本就保持不动了，很少有分裂。
  • 这意味着，很多时候某次迭代写入叶子节点的数据，就真的是最终叶子节点的数据。
• 基于此，作者设计 iSax2+ index算法。
  • 第一轮迭代，和iSAX2.0完全一致，数据和SAX全部写入叶子节点；
  • 从第二轮开始，仅在分裂时有差异。分裂时，不再从节点中读出所有源数据，只读SAX表示用于分裂，磁盘中的SAX和LBL中的序列+SAX分裂入新的叶子节点进行存储。这意味着中间节点也会指向数据文件。
  • 在数据源完全过了一遍之后，对iSAX树内中间节点的数据向下传导至叶子节点，以DFS顺序遍历，使用LBL，将叶子节点内的原始数据补齐。
    • 这个过程是很快的，因为读上来的数据都是在特定的子树内的。

5 Experimental evaluation

Intel Xeon E5504 with 24 GB 内存, 2TB Seagate Barracuda LP 硬盘, Windows Vista Business SP2. 编程语言： C#/.NET 3.5 Framework.
5.2节case study所用到机器
AMD Athlon 64 X2 5600+ with 3 GB 内存, 400 GB Seagate Barracuda 7200.10硬盘, Windows XP SP2 (with /3 GB switch).

• 首先是SAX的紧密程度。可以看到每段基数大于50时，SAX就足够不错了。

  
  image.png

5.1 Scalability of iSAX 2.0

5.1.1 Splitting policy evaluation

100million 长度256 random walk 数据集
新的分割策略，使得分割更为均匀，叶子节点更少，叶子节点负载率更高，索引大小更小。
【注意下图第一个图的纵轴时间单位应该为小时，而非分钟】

image.png

5.1.2 Bulk loading evaluation

• 100million构建不足16h

  
  image.png

5.1.2.1 iSAX 2.0 Clustered and iSAX2+

image.png

5.2 A case study in entomology

【略】