标题：PARROT: 大型分区时间序列基于模式的关联挖掘

编者的总结

1. 本文针对的是大规模分区数仓里的时序非聚集索引，这样一个新问题，且要求分区属性包含较强的语义：分区内的序列应基本相似。基本思路是在每个分区内将序列的SAX表示聚类，再在全局整合相同的聚类中心，索引结构则是倒排链表。
2. 核心的技术贡献在于提出了如何聚类，基本思路是在SAX空间中，按照权重排序，依次尝试作为新的聚类中心（需保证不予已有聚类中心覆盖区域重叠）；所需的参数作者选择转化为一个用户友好的超参代替，然后根据这个超参的限制条件进行grid search选取合适的参数对；
3. 另一个技术贡献在于可以评估全局聚类质量，和传统聚类评估不同，本文的问题下希望分区内的序列越相似越好，至少能有规律的遵循少数几个模式。因此评估手段是聚类结果和标量分区属性是否存在一定的信息关联。如果关联弱，索引性能急剧下降。

• 本文的模式(pattern)可以理解为在SAX空间上，聚簇成几个密集的坨。期望是分区内是少数几个超级大坨，糟糕的是稀疏分布一大片。

编者的思考

1. 将SAX空间连续化考虑是一个创新点。之前TARDIS,Coconut尝试将低维的SAX表示排序，往往会破坏高维的邻近性，在连续空间上则没有这个问题，各个维度（分段）可以被平等地考虑进去。
2. 本文研究的问题也比较新：大规模数仓里的非聚集索引。非聚集索引一直研究的都比较少，在数仓上的更是没有，所以实验中SOTA都是扩展而来。
3. 注意是一个静态索引；
4. 查询功能弱：无法剪枝，近似查询无保障，无法精确查询。
5. 使用的都是首次出现的数据集，会不会PARROT对数据集是比较挑剔的？
6. 异常处理机制感觉还是比较弱，一个异常的主模式里的SAX表示可能包含太多分区了；另外最终的异常点每次都要比较其实也是潜在的比较大的开销，按数据集的分布来定了。

1 Introduction

1.1 Background and motivation

• 作者讲精确搜索代价太高因此不常用，精确匹配又有可能序列根本就不在数据库里，所以精确相似性查询不受欢迎，近似查询更受关注。
• 在数仓中，时序数据的分区属性是很简单的，一般就是时间或者空间属性；在同一分区里的序列应当存在共同的语义（比如同一地点，同一日期等），有着较强的相似性。
• 过往索引都是主索引，构建时间长，存储开销大；
• 本文想要构建二级索引；观察到每一个分区内的序列都遵循一个或多个模式，则我们可以对这些模式和其与分区属性的关系做索引；这样做的一个好处是分区内的数据局部性得到保留，跨分区的数据计算可以节省掉。
• 另外要注意到，数据在一个分区里的模式不可能总是全局独一无二的，在一个分区里出现的模式在另一个分区里也有可能出现，彼此之间是可能有重叠的。

1.2 Challenges in correlation-based searching

利用数据关联性做查询优化在RDBMS（~2010年）和大数据（~2015年）上都有做过，但时序数据上没做过。

1.2.1 分区级关联

• RDBMS中的关联主要是列之间的关联，比如两列之间有一定的数学关系，则可以根据索引情况纳入查询优化器考虑范围；
• 作为时序相似性索引，我们希望能在查询时判断出和Query最相关的几个partition，再从中筛选具体的序列。

1.2.2 高维的关联关系很难寻找

1.2.3 软关联的判定与异常处理

一个分区里的序列有时候不一定满足统一的关联关系，如何判定一个关联是否强，以及异常序列如何处理也是一个挑战。

3 Pattern-based representation

3.1 PARROT overview

索引构建流程分5步。

1. 每个分区抽样，评估关联强度，设置关联参数；
2. 逐分区确定pattern，得到主模式和异常；
3. 基于主模式逐分区构建本地索引；
4. 异常统一处理，尝试寻找跨分区异常模式；
5. 基于主模式和异常模式构建全局索引；

image.png

3.2 P-Pattern abstraction

• 每个分区包含几十万序列。如果直接将分区属性和每一条序列建立映射，寻找关联，则过于笨重。原因如1) 计算量极大 2) 大量关联可能是类似的、冗余的。
• 所以本文的思路是首先提取模式，即P-pattern，然后寻找模式和分区属性的关联。

• 每一个模式代表一组相似的序列；一般来说模式数量少，维度低。

  
  image.png

3.3 P-pattern definition and construction

首先对每条序列降维做准备工作：

1. 求每条序列的SAX表示；
2. 将序列按照SAX表示分组，得到频率（权重）；
3. 把SAX表示作为低维空间一个有权重的点。

之后准备生成P-pattern。

• P-pattern是一组点，这组点距离锚点的距离都小于半径参数r。实际上，P-pattern就是SAX空间上的一个球形空间。
• 我们要做的就是把刚才得到的这些点分给若干pattern，要求彼此互斥（没有点在两个pattern里），且最终得到的pattern数越小越好。
• 注意到r是一个固定值，而固定大小的球是没办法填充满一个空间的，所以作者的解决办法是让r取两个值，0或者r。
  • 另一个思路是不固定r，即每一个P-pattern都有不一样的r，但是计算复杂度太大而且解不出来，因此放弃。

具体的方法很简单：

• 首先按照权重降序排序这些点；并初始化patterns集合为空；
• 如果当前点和patterns集合中所有锚点的距离都大于2r，则创建一个新pattern，并扫描点集合：与当前点距离不大于r的从点集中删除，进入新parttern。
• 否则的话（即，用当前点创建新parttern会和已有pattern重叠，但又不位于已有的pattern内部；比如和所有锚点的距离都是1.5r），保留在点集内部。
• 当所有点都扫描一遍之后，点集中剩下的点就是r=0的self pattern。

注意这个算法最终找到的肯定不是最优解，是一个贪婪算法。

4 Correlation management

• P-pattern的总数少，pattern内的权重高（基数大）暗示着这个分区内的序列确实遵从着一定的规则。

4.1 Significant and exception P-patterns

• 主模式和异常是按照权重来分的，注意这和半径是r还是0没有关系，单独一个高权重点，也是主模式（代表大量的序列形状都非常相似，即同样的SAX表示）。
• 具体区分规则是用一个参数定死，权重就是在分区内的比例了。
  • 到这个位置已经有两个重要参数和需要为每个分区确定了，这一过程是自动确定的，将在第五节介绍。

image.png

4.2 Metric of Correlation Strength Evaluation

本节要判定的是关联强度，即分区属性是不是和P-pattern有较强的关联。采用的主要是信息论的方法，即分区属性带来的信息量，和已知分区属性后，主pattern能带来的信息量之差，这个差值越大，说明分区属性某种程度上已经能够决定pattern了，那么分区属性和pattern之间的关联就越强，最强是1，最弱是0.

image.png

5 PARROT indexing framework

5.1 Index construction

5.1.1 关联强度判定+pattern参数确定

• 要想判定关联强度，需要知道主模式和异常；主模式和异常的划分需要参数和；如何自动化寻找参数和呢？
• 本文的方法是让用户提供一个参数，即数据集里的异常点最大比例，根据的限制条件，PARROT网格搜索和，若满足则计算关联强度F'；最终在所有考虑的参数对中，选择F’最大的那个。
• 这一步是抽样来做的，所以整体数据规模较小，做grid search问题也不大。
• 这一步的结果要么是一个参数对，要么是没有满足条件的关联关系（不能使用PARROT）。
• 注意这里的和是全局唯一的，各个分区都采用相同的参数，不然度量标准不统一，对主模式和异常的判定会有口径不同的问题。
  image.png

5.2.2 P-pattern挖掘

根据上一步的参数对结果，投入全部数据，挖掘出P-pattern，包括主模式和异常。主模式进入第三步，异常进入第四步。

5.2.3 本地索引构建

• 如下图，本地索引结构非常简单，在每个分区内，存一下各个pattern，包括锚点，基数，pattern中包含的点，对应的具体的序列id，就是一个倒排链表。

• 另从中抽出P-pattern信息发给master，参与全局索引构建。

  
  image.png

5.2.4 异常处理

• 作者发现，各个分区的异常点如果汇总起来，作为一个新的异常分区，也会产生一些新的主模式，于是可以把相同的P-pattern挖掘算法再用一次，唯一的不同就是除了保存序列id，还需要保存这条序列所在的分区。

• 仍然是异常点的，就只能顺序放在文件里，集群中每个节点放一个文件，存储这些异常。

  
  image.png

5.2.5 全局索引构建

全局索引也非常简单，就是把所有主模式放在一起，整合其中相同的部分，计算全局基数，就是全局索引了。

image.png

5.2.6 小结

索引结构包含4部分：

1. 全局索引（常驻内存）：倒排表，指出有哪些锚点（主模式），对应哪些分区；
2. 本地索引：倒排表，指出有哪些锚点，包含哪些点和序列；
3. 异常索引：倒排表，全局的异常分区，指出有哪些锚点，包含哪些点和序列；
4. 异常文件：一批文件，存储异常点。

6 Query processing using the PARROT index

（近似kNN）查询分三步走：

1. 扫描全局索引，找到和query最近的几个主模式，只需要这几个主模式的基数>k即可；
2. 根据全局索引的指示，找到对应的分区：
   • 如果是正常分区的主模式，则计算和SAX表示的距离，取其中>k个SAX表示即可；
   • 如果是异常分区的主模式，则要找到对应的分区在哪里；
   • 异常文件也要全部加载然后计算近似距离；
3. 每个分区返回给master若干个SAX表示，保证总基数<=k；然后master根据报告的位置去取真实序列，计算真实距离，返回topK.

7 Experiments and system evaluation

7.1 Prototype, datasets, and experimental setup

spark scala编写。

• 环境：112 Intel@Xeon E5-2690, 1TB RAM and 15TB SATA hard drive.
• baselines: Dss（分布式顺序扫描），Vss（分布式VA-file），TARDIS。
• 数据集：卫星图像数据集，路口监控视频数据集，随机游走数据集

7.2 Algorithm-centric high-level summary

因为本文的方法实际上是针对了一个新问题，所以下图是和其他方法作区分用的。

image.png

7.3 Evaluation of query execution

• 整体查询方面的性能和聚集的TARDIS能差不多，且访问的分区数还明显要少一些，说明达成的查询质量还是很不错的。

  
  image.png

• 继续放大k，查询性能也过关。

  
  image.png

• 不同的数据集大小，差异不大。

  
  image.png

7.4 Evaluation of index construction

构建时间上由于是非聚集索引，所以肯定是很快的，从图中可以看出限速步是本地索引构建，也就是寻找P-pattern的过程。

image.png