标题：大时间序列数据的分布式索引框架

编者的总结

1. 本文针对分布式环境，做time series的whole-matching，基本上只做了近似情况下，是对2017DPiSAX，几乎做了全面的优化，无论从分析上还是从结果上来看，几乎都是完全的outperform的。
2. 本文最突出的亮点是一颗compact的iSAX树，这颗树深度很小，足够紧凑，最重要的是，叶子节点中的序列之间的proximity，得到了很好的维护，因此，显著提升了approximate KNN的结果质量，实验中召回率在30%-60%之间，也证实了这一点。

编者的思考

1. 本文对Exact query的定义过于另类（距离为0），实际价值也不大，对于exact knn的搜索，还是一个问题。
2. 本文核心思路和DPiSAX还是很像的，通过sample分割dataset去几个disjoint的partition，建立global index和local index两级threshold。这种思路的一个问题就是单查询几乎毫无裨益，对吞吐量的帮助倒是很大。
3. 还有一个问题就是近似准确度的问题，召回率不太稳定，也没有保证。

ABSTRACT

首先提到iSAX的扩展性一般，扇出太小，通常是二叉的，导致树很深，不利于延展。
另外一点是这个character-level的分割会导致叶子节点里的series之间的proximity很差，极大的影响了KNN的质量。
本文提出的TARDIS也是iSAX-based index tree，但是解决了上述问题，可以做精确和近似的KNN。TARDIS是word-level进行分层的，支持压缩的结构，高效搜索和比较，相似关系也得到了很好的保留。
本文的索引可以支持G级别的time series个数。实验中，在速度、空间和质量上都得到了较大提升。

I. INTRODUCTION

首先说SOTA的方法，既没有准确性，也没有扩展性。
iSAX系列的都是中心化方法；一些TSDBMS主要用的是数学模型；DPiSAX和本文最为类似，但是中间节点太多了，树太深了，另一方面bit太多，比较太耗时。
本文提出的就是变长的word-level的基数，word-level更适合并行处理

II. PRELIMINARIES

exact query定义的比较奇怪，要求找到与query time series ED距离为0的所有序列。

近似是用error rate来定义的

image.png

iSAX的缺陷：

1. 树的层数太深，查询的时候每层至少查一个；
2. 初始为每个时间序列留出了足够大的基数，这造成了冗余计算；

3. 基数不同进行归档(character-level)，导致了同一leaf node里面的ts，相似性没那么好，假阳性和假阴性都大量存在，导致了近似结果较差，如下图。

   
   image.png

DPiSAX的缺陷：

1. 继承了iSAX的所有缺陷；
2. 缺失了refine的阶段导致了精度退化（？）。

III. TARDIS BUILDING-BLOCK STRUCTURES

A. iSAX-Transposition Signature (iSAX-T)

首先是word-level，表示树的每一层，每个word的基数都是一样的；另外是transpositition，如下图，先转置然后取16进制。这样表示之后，对基数进行降级就可以很方便的删去右面的几位。

image.png
image.png

其实从数字上来看，就是把每个word的头一位拿出来拼起来做十六进制第一位，其他位也是一样。

B. iSAX-T K-ary Tree (sigTree)

image.png
sigTree就长上图的样子，每个内部节点的扇出最多是个，因为孩子节点相对于其父母节点，是对每一个segment后面补上一位(0/1)，每个segment两种选择，共种选择。分裂的策略也是满了就溢出。另外，每个指针都是双向指针。

sigTree的好处有几个：

• 深度肯定降下来了；
• word-level相似性肯定强了；
• word转换很快（transposition）。

IV. TARDIS INDEXINGSTRUCTURE

A. TARDIS Overview

主要流程就是下图，一个TARDIS-G，一个TARDIS-L，在TARDIS-G查好partition，再去TARDIS-L具体找序列。

image.png

给一个初始基数，两种index的分裂threshold，一个word-length，就可以开始构造索引了。

B. TARDIS Global Index (Tardis-G)

数据集以block-level进行采样，以一个初始基数得到一个(isaxt(b), freq:1)，然后按照isaxt(b)进行reduce，得到(isaxt(b), freq(b)).

接下来，算法会依次对每个layer进行迭代，注意layer就等于iSAX word的基数，迭代过程，就是逐渐将基数+1.

不失一般性，我们以第一层为例，把isaxt(b) map成isaxt(1)，对于isaxt(1)再Reduce sum一次，我们就得到了TARDIS-G第一层各个节点，以及每个节点的频数；之后我们筛出来频数超过th的，它们是需要继续分裂的节点，不需要分裂的，自动成为叶子节点。
接下来就是第二层，把之前需要分裂的节点中的序列的isaxt(b),freq(b)拿出来，再map 成isaxt(2)，再Reduce成freq(2)，得到TARDIS-G第二层节点，后续依次类推。

构建好树之后的问题就是给他们分配partition，规定只有兄弟叶子节点才能在一个partition，一个叶子节点只能在一个partition。那么问题就可以抽象成，给定一组兄弟叶子节点，和一个partition的capacity C，如何分配尽量少的partition，装载这些叶子节点。类似变形的背包问题。
采用的方法是个贪心，First-fit策略。
叶子节点的partition也要向上让它的祖先知道，得到归纳。

C. TARDIS Local Index (Tardis-L)

首先是广播TARDIS-G，按照这个索引进行分partition。然后是对partition内部的构建，内部主要用插入的方法来构建，满了就分裂出来至多个孩子，然后重新平衡。

为了支持快速的精确查找，使用了bloom filter布隆过滤器，以确定某个元素是否在某个集合内，可能出现假阳性，但不会出现假阴性。bloom filter在插入索引的时候把isaxt(b)插进去就行。

V. TARDIS QUERYPROCESSING

A. Exact Match Query

由于本文exact query的特殊定义，只需要通过TARDIS-G找到对应的partition，再查下bloom filter，如果阳性，就去走下TARDIS-L，以判断是否存在即可。

B. kNN Approximate Query

朴素的方法是通过TARDIS-G定位到partition，沿着根节点往下找，知道找到一个最低的且freq大于k的节点，把它里面的全都load出来，计算KNN。

精确度再高点，把整个节点的load出来，利用上一个方法的KNN做lower bound剪枝。

精确度再高点，把该partition的兄弟节点的partition都如此并行处理，最后按照距离归并排序就可以了。为了避免选出来太多partition，用一个pth作为threshold，超过了的话，就随机抽。

VI. EXPERIMENT

召回率和error rate提升比较明显，average query time基本持平

image.png

local index size有一定压缩。

image.png
索引构建时长有减少
image.png