TB级别time series data的索引和挖掘

编者对文章的总结

本文基于SAX提出了iSAX，是对时间序列的一种抽象表示法，可以动态扩展其维度，以此构造树形结构的索引。这种索引主要的功能是应对相似搜索(similarty search)，其它功能作者并未提及。在similarty search中，近似结果的获得是非常快的，在秒的级别；精确结果的搜索性能则不太稳定，在几十分钟到几个小时这样一个级别。近似结果的质量有较好保证。
另外，虽然说是TB级别的索引，本文的场景是离线序列分析，而且侧重于多序列，短序列的场景。比如100M个序列，每个序列长度256，大小0.5TB。
文中也举了一些例子，合理组合近似查找和精确查找，可以高效解决一些Data Mininig算法问题。

编者对文章的思考

1. 首先对于长序列，iSAX的质量和能力作者并未说明，可以想到，对于长序列，也可从中折成几段进行存储，但究竟质量和性能如何，以供之后研究。
2. 由于作者研究的是海量短序列，于是就把形状相似的若干个短序列存在一个文件中，作者这样做是为了展示其通用特征，编者认为若能用合理的文件存储格式、压缩方法和内存缓存，以减少IO代价，性能将有更大的突破，以供之后研究。
3. 索引创建的时间和效率作者仅提供了插入算法，没有性能的实验数据，推理应该和一次精确查找差不多，和内存大小关系比较大。
4. 本文研究的是离线分析，iSAX能否加以改动能否用于线上的实时分析呢？
5. 本文提供的iSAX索引，仅可用于similarty search这一种情形，基于iSAX的思想，能否构造出其它索引，或者更通用的索引结构，用于更灵活的query需求呢？

Abstract

做了一种符号化的representation来索引TB级别的dataset。
可以做快速的准确查找和极快的近似查找。

1. Introduction

Million级别的time series个数，TB级的空间占用，进行索引。
iSAX基于SAX的一种变体，以获得可扩展的哈希。iSAX同时也是SAX的超集，所以用SAX的同样可以用iSAX以获得扩展性。
iSAX速度，适用性，扩展性上都很好，所以实验直接用的Windows XP NTFS文件系统，并没有用特定的DBMS。

2. BACKGROUND AND RELATED WORK

2.1 Time Series Distance Measures

一般对于time series 距离的计算，主要是两种，一种是欧氏距离ED，一种是动态时间弯曲DTW。由于本文研究的是大数据量级的，所以ED和DTW差距不大，用的就是ED。当然文章也补充说可以稍作修改变成基于DTW的。
对此，文中做了一个实验，补了一句解释：

image.png

The well-documented superiority of DTW over ED is due to the fact that in small datasets it might be necessary to warp a little to match the nearest neighbor. However, in larger datasets one is more likely to find a close match without the need to warp.

2.2 Time Series Representations

现有的representations如图。

image.png

其中带星号的都有一个优良的性质，就是下界性。具体来说，就是对time series，我们可能会做abstraction，对这个abstraction进行距离计算的结果保证不超过对真实距离计算的结果。只可能更小，不会更大。

2.3 Review of Classic SAX

这是对之前SAX论文的回顾。
首先是回顾了PAA，PAA将一个时间序列分割成w段，各取均值，构造成一个w维向量，放入w维空间。
然后是SAX，SAX首先根据高斯分布N(0,1)，按照参数a，分割成等概率的几个部分，返回相应的x值，这些值被称为breakpoints，用于分割时间序列，如下图。

image.png

借助刚才的PAA值，如果PAA值落在某两个breakpoint线之间，就被赋予一个特定的符号，这里我们用二进制来表示了。这样的话，时间序列就变成一个w维的向量，每个元素都是一个符号/二进制数。
刚才的参数a，称之为基数，它主要决定二进制数的长度。这个基数可以随意变化，变得大一点，各个PAA segment之间的就别就更明显一些。对于2的幂次，还有一定规律。

image.png

基于SAX，我们可以为两个时间序列定义距离，这个距离肯定是小于欧氏距离的，源于SAX下界的性质。

image.png

公式中dist这个函数，竟然是通过查表来获得结果。

image.png

这个SAX距离究竟比欧氏距离小多少呢？作者做了一个实验：

image.png

可以看到当基数a比较大的时候，SAX和PAA就差不太多了。而且即使当a=256，每个PAA segment也只需要8bit来表示，但是PAA方法需要用一个浮点数32bit来表示，就产生了差距。

3. THE iSAX REPRESENTATION

3.1 Comparison of iSAX Words

本文的一个贡献就是，即使两个序列用了不同基数做SAX变换，仍然可以进行距离计算。

image.png
以上图为例，一个序列以8为基数，一个以2为基数，如何进行距离计算呢？
首先说一个“定理”，SAX空间中的两个基数a<b，如果有公因子（除了1以外），那么a中的breakpoints是b中breakpoints的子集。
接着说距离计算，对进行基数提升至，只需要对于每一个元素，找到以部分为开头的符号/二进制数中，在SAX空间距离最近的就可以了。
那么肯定有疑问就是这和原本的时间序列进行SAX，以8为基数的变换形成的真可能不一样。确实。不过我们提供的本来就是一个下界，这个下界再“下”一点也仍然是下界，更何况，我们不能从失真的压缩中解压成真实的出来。

4. iSAX INDEXING

4.1 The Intuition Behind iSAX Indexing

本文的索引主要是用于一个相似性的查找。文中举了一个例子，比如基数为8的，SAX word长度(w)规定为4的这样一对参数，可能产生的不同的iSAX向量个数为。那么磁盘就分成这么多文件，每个文件只放相应的时间序列。
在查找的时候，想要找到相似的时间序列，只需要将输入的时间序列进行iSAX变换，取出对应区域的时间序列，一定相差不多。如果一定要精确的距离最近的，那么首先计算最佳近似的序列和输入序列的真实距离，然后遍历所有LABEL，如果其MINDIST比当前最短的距离要短，那么也计算这个LABEL下的所有序列和输入序列的真实距离。

然而上述所说在实际应用中仍然有一个致命的问题，就是数据倾斜。一个文件中可能存放了特别多序列，也有可能很多文件是空的。空的话查找时就要用一些trick，序列太多的话，明显会影响性能。一个方法是设置一个参数，让一个文件中的序列个数在[1,]之间。
既然设置了上限，就必须要有分割文件/Label的方法。其实就是在SAX word中随机选一个进行2的幂次扩增，1次能扩增成两个文件，以下图为例：

image.png
对原文件中的每个序列的某一个PAA segment重新计算PAA值应该落入的区域，然后分入两个文件里。
整个算法原理就是扩展性哈希的原理。（这个应该在《数据库系统概念》中讲哈希索引的位置有讲到）

4.2 iSAX Index Construction

用一个索引树，对SAX空间进行分割。然而实际实现中，文中并没有用树的结构，而是用了一个哈希表。

image.png

文中提供了一个插入的伪代码，根据图示很容易得到，不详述。

4.3 Approximate Search

近似搜索只需要在树中找到对应的叶子节点就可以了。把叶子节点指向的文件中的序列取出来，在内存中遍历做下欧氏距离计算，选距离最近的那个即可。
没有对应的叶子节点，就会对应到一个内部节点，这时就需要用兄弟分支做一个近似，文中没有细说。

4.4 Exact Search

精确查找麻烦一些。第一步先确定一个近似查找的BSF(Best-So-Far) Answer，方法如上一节。之后从根节点遍历这颗树。用的数据结构是一个优先级队列，大小比较方法，就是节点的label和query的序列距离的下界。这个下界可以用之前定义的MINDIST，但是文中还提到了一个更“紧”的下界，基于query的序列是完全暴露可知这一条件：

image.png

对于label中的每一个维度，能够确定原本序列在该segment的PAA值的一个区间，即(,]，如果query序列，即T，其在这一segment的PAA值如果落在了区间内部，则距离为0,；如果落在了区间外面，就是和边界的距离。这样计算得到的一个下界，比MINDIST更紧。

接着说算法，每次从优先级队列出队，如果队列为空，或者出队元素的DIST比BSF还要大，那么直接break掉，BSF就是最优解；
否则的话，如果出队的是内部节点或者根节点，则计算其所有孩子的下界距离，然后入队；
如果出队的是叶子节点(terminal node)，就要取来index file，将其中所有序列和T(query序列)做真实距离计算，更新BSF。
文中还提到，目前是1NN问题，KNN问题稍作扩展也是可以的。

5. EXPERIMENTS

5.1 Tightness of Lower Bounds

首先就是对比iSAX这种表示法和其它表示法之间的区别，主要是看这个表示法计算出来的距离的下界够不够“紧”，形式化的描述是：

image.png

实验的结果是iSAX是TLB最高的：

image.png
但在这里我觉得有必要说明下，这里是固定了字节数的，就是每个时间点用几个字节来表示(?)，那么一个32位/64位浮点数被切割的话，下界的性质也是很难保证的。而iSAX这种表示法，充分运用了每一bit的信息，效率最高。

5.2 Indexing Massive Datasets

文中首先对近似搜索的结果的准确性进行了核验：

image.png
从图中看出，近似算法返回的是距离头一百名的序列概率有90%以上，头10名是50%左右的概率，直接返回精确结果仅有10%-15%的概率。
要注意到，这个近似算法是非常快的，一次磁盘读取，至多次欧式距离计算，耗时不会超过1s。

对于精确查找，在1M，2M，4M，8M的数据集上，分别产生了 [2115.3, 3172.5, 4925.3, 7719.1]次磁盘搜索，耗时分别为 [3.8, 5.8, 9.0, 14.1]分钟，相比于顺序化搜索的 [71.5, 104.8,168.8, 297.6]分钟，还是有较大提升。

作者为了试验这个方法的极限，把序列个数上升到1亿条，即100M，总大小0.5TB。再次做近似搜索，时间仍然在1s-2s这个范围内，对于搜索质量的衡量，就是判定搜索结果在KNN中的排名，作者也强行去找了，发现排名平均为8，最差一个也有25名，还有3个直接找到了第一名。那这个结果就很有意义了。
精确查找作者也做了，平均时间在90min左右一次，相比于顺序查找的1800min，已经有很大提升了，但是仍然很难讲实用。

5.3 Time Series Set Difference

作者把这个索引用于一个实际问题：给定两个time series set A和B。在A中任取一个times series T，使得T与B中的1NN序列的距离是最大的，这个最大距离就是A和B之间的difference。
要说明的也是性能提升，没继续细看。

5.4 Batch Nearest Neighbor Search

一个基因对比的问题。

6. Conclusion

本文提供了近似搜索和精确搜索相结合的例子，还有其他算法可以因此而获得提升，比如motif discovery, density estimation, discord discovery, and clustering。