标题：ChainLink：对大量数据数据进行索引以支持长的subsequnce matching

编者的思考：

1. 本文的致命伤就是只能提供近似结果，没办法提供准确结果，以至于实验比较的时候，是用近似的时延对比其他方法的精确时延，有一定误导性；即使是近似结果，召回率也太低了，近似的质量不够好，也没有一个很有力的解释，只能通过error rate来表示即使不是exact KNN之内，也有一定意义。
2. 还有一个问题就是本文虽然也是通过切割chunk的方式来支持变长查询，但是不能支持变长的NSM查询。
3. 实验中没有统计索引的筛选率如何，本文是一个chunk相似，就把整个subsequence拿出来算一次真实距离，没有考虑chunk间的关系，不知道筛选率相比于其他方法如何？
4. ChainLink索引的本质是先拆分chunk,在每个chunk内部对overlapping, continuous的subsequences进行归纳（分散，n-gram，哈希），抽取特征（哈希表中的元素），和query进行match。其结果是基于概率进行保障的。

主要亮点在于长Query，SOTA中的方法，普遍对于长Query的subsequence matching支持的不太好。

ABSTRACT

目前，SOTA的subsequence matching在TB级别的序列上就很难用了。不止是索引构建时间，查询时延也会退化，当query长度超过了几百的时候。
LSH给出了一个基于哈希的解决方案，但是其hash函数需要多次遍历series不现实。
本文提供了一个轻量级的分布式的索引框架ChainLink，以支持TB级别的近似KNNsimilarity search。
为了支持ChainLink，还提出了一个新型索引技术SPS(single pass signature)，SPS解决了上述索引问题。
Scalable的索引构建分三步：

1. 每个分区内部，数据重组以支持高效随机访问；
2. 每个分区内部，基于SPS技术，并行的构建本地索引；
3. 整合压缩所有分区索引，构建一个中心化的索引，可以在查询中做到高效剪枝。
   上述三步，ChainLink可以在一个MapReduce过程里完成。
   实验测试，索引大小仅占不足原数据2%，索引构建时间较之前也有两个数量级的提升；最终结果的时延提升10倍，准确率提升15%。

1. INTRODUCTION

A. Background and Motivation

讲了两点，一个是量大需要现代分布式计算设备，一个是KNN是DM的核心需求。

B. Common Problem Characteristics and Technical Challenges

1. 为什么是近似的？一方面是近似结果质量很好，足够用了；另一方面，近似结果能提供的优化也很多。
2. 为什么是分布的？这么大的ts data，一般都存在hadoop,kudu之类的FS里面。
3. 为什么要long query？引用中有提到。本文要研究k级别的query长度。
   那么本文就要做近似的分布的long query的算法，挑战如下：
4. 高维度：R-trees在高维下性能不行，UCR Suite也因为loose bound而失效。作者的方法是哈希，a novel哈希，既能保留原有特征，又能降维。
5. 重要的overlap：KV-match枚举过于昂贵。用了一个基于两元论的方法，能生成disjoint的subsequences。
6. 随机访问：两个序列的子序列可以非常相似，但他们的母序列长得非常不一样。subsequence matching更有可能触发的是Random-access，每个series都有可能成为备选,hadoop和spark的全分区扫描太低效了。作者是用双层索引来解决这个问题的。
7. 速度和准确性的trade-off：SSH那篇扩展性不行，本文目标要有扩展性。作者的哈希技术，既有20倍的速度，又不牺牲准确性。

C. Limitations of the State-of-the-Art

KV-match，索引创建太慢，占用空间太大；
VI-table，限制了query的类型；
这两个放到Hbase里面的设计也有问题。
UCR Suite问题已经说过，做成分布式由于频繁的通信，性能也有所下降。

2. Preliminaries

A. Key Concepts of Time Series

其他都稀松平常，只有一个近似的定义需要提出来：

image.png

X是近似结果，Y是精确结果，平均差值距离，不能超过一个界限。

B. Background on LSH

3. OUR PROPOSED CHAINLINK INDEX

A. ChainLink Overview

Chainlink可用于分布式内存数据，也可用于磁盘数据。本文以spark rdd为例。

B. ChainLink Local Indices (CL-Local)

CL-local的建立分4步来走：

1. Record Organization:ts要以数组形式存储，能够做到随机访问。
2. Chunk Generation：每个ts划分为若干等长的不相交的chunk，之后对每一个chunk为基本单位进行操作。
3. Chunk Feature Extraction: 对每个chunk做特征抽取，同时降维成一个低维向量；随后对这个低维向量做n-gram生成，得到一个权重集。
4. Hashing：对每个chunk的权重集进行分段哈希，每段的哈希结果进入不同的hash table。

Step 2 (Chunk Generation)：

每个chunk长度是w（用户参数），有关w的具体如何设置，和query的workload和最小长度有关，在两元论那篇文章中有描述。

Step 3 (Chunk Feature Extraction):

两个过程，一个是sketching，一个是n-gram。

image.png
首先是sketching，方式如图，其中r是一个随机向量，从高斯分布里随机抽出来的，其长度|r|是一个用户参数。还有一个用户参数是步长。结果生成的是一个降维过的布尔向量。
对于这个方法产生了Lemma1：
两个chunk欧式距离如果无限小，sketches一样的概率接近于1。

然后是n-gram。
n是用户参数，决定n位的窗口，然后滑动窗口进行计数，得到n-gram的权重集。如图。

image.png
显然，权重集是个整数的向量。

给了一个定义Hamming距离，即两个向量相同位置不同元素的个数。
对于这个方法产生了Lemma2：
如果sketches相似，权重集也相似。
具体来说，两个sketch的Hamming距离是1，其权重集的hamming距离不会超过2n。这相比于来说很小。

Step 4 (Hashing):

首先说得到的权重集是非常稀疏的，绝大部分都是0。
文中提出的SPS哈希，就是把得到的权重集分成g个bin，每个bin做哈希即SPS，如下图第一个箭头和算法。

image.png
image.png

得到了signature之后，再把每个chunk的signature分成b个band，对每个band再做哈希，分别进入各个哈希table，如上图第二个箭头和下图算法。

image.png

b*r=g。这个b和r的选取还有一定讲究。

image.png
这个s就是JS：
image.png

s这个参数会决定至少以多大的概率，两个signature会在至少一个hashtable里share一个bucket。

基于这两个哈希过程，又有了Lemma3:
如果两个权重集的Hamming距离<=2n，如果g=2n，经过哈希，chunk将至少在至少一个哈希表碰撞。

基于以上3个Lemma，得到定理：
如果两个chunk距离接近于0，他们在至少一个哈希表上的碰撞概率接近于1.

C. ChainLink Global Index : CL-Global

由于CL-Local所有partition都采用同样的参数，同样的算法，会得到同样意义的b个哈希表，CL-Global把CL-Local集中起来，建立总哈希表，key是tbl_id+bucket_num，value是partition的list。CL-Global只包含Local的key信息。
整个索引建立的过程，可以用map-combine-reduce过程完成。

4. CHAINLINK QUERY PROCESSING

image.png

把Q分成若干chunk，分布式的计算其哈希，收回master和CL-Global进行检索，把涉及到的partition发回worker进行本地搜索。worker找到其对应的具体ts和chunk抽出对应的subsequence，在本地求KNN，求完之后，发回master做全局KNN。

5. EXPERIMENTAL EVALUATION

首先是索引创建时间和大小，这点上比较优良，符合预期。

image.png

然后是query response time以及结果质量，有数据集大小/Q的长度/K的影响。
首先是Q的长度对于时间效率的影响微乎其微，这是优良的性质，主要由于其分布式的特性。
从error rate率上来看，平均只有2左右的差距，效果还不错，但是召回率，就太差了，只有不到30%。
作者的解释是，虽然不是确切KNN里的结果，但是从质量上来看也是很近似的。

接下来是和UCR的比较：

image.png

然后是KVM的比较：

image.png

（一个问题是，上述两个算法是精确的，Chainlink是近似的。。。）

最后一个是并行度的考量：

image.png

query response time没什么变化了，并行度顶天了；索引构建倒是并行度很高，毕竟没什么通信时长。

6. RELATED WORK

whole matching
centralized subsequence matching
simplified distributed subsequence matching
KVM, index size too large