标题：通过跨范围限制进行动态覆盖构建的时间序列索引

Abstract

• 本文做的是DTW的索引，基于DCRC来做，即（Dynamic covering with cross-range constraints），目标是Efficiency和Scalability；比基于超矩形的方法要好。
• 可以定义下界距离。
• 可以建立层次化索引HDCRC。

3 Dynamic covering with cross-range constraints (DCRC)

3.1 DTW

3.2 ACM-relationship

下图这样就叫ACM-关系，从左下到右上，要么往上走一格，要么平走一格。

• 如图横轴是m，纵轴是n。ACM关系可以用于将一个n长度的序列，延展成一个m长度的序列。

• 以图a为例，原序列可能是x1,x2,x3. 经过转换后，就是x1,x2,x2,x3,x3.

  
  
  

  image.png

• 有了ACM关系之后，我们就可以度量两个不等长序列的距离。

• 具体来说，要找到一个ACM-关系r，使得用r将短序列延长后，和长序列的欧式距离最小。

• 这个延展后的欧式距离就是新度量D，关系r就是对应的ACM关系。

3.3 Approximate subsequence

ACM关系可以用于将短序列延展伸长，本节讲的近似子序列AS，可以用于将长序列变短。
基本方法就是分段做均值。问题是如何分段？

• 给出一个目标函数：变短后的序列和原始序列的D最小。
• 至于具体怎么找分段，粗暴的方式就是遍历所有排列组合，分别计算D。也可以用动态规划减少搜索空间。

3.4 Covering set

这一节讲如何利用DCRC来聚集时间序列。

• 使用DCRC需要一个参考序列c，它的维度是比较低的，设为n。数据库里的时间序列长度较长，可以设为m。
  • 理论上参考序列越中心越好，实际情况c是数据库里任意选的序列，通过AS方法缩短之后成为的c。
• 之后对于数据库里的每一条序列ts，去找和c的最优ACM-关系r。
• DCRC如下图，m个维度，每个都有一个自己的格子，每个格子里面包含真实序列的范围（可能来自周边的多个维度，由于DTW的动态范围）。
  • 举个例子，中间第三列，表示DCRC的第三个维度，包含真实数据集中序列第二个维度的范围，和第三个维度的范围。
• 刚才我们算出了ts和c的最优ACM关系r，它就是一条DTW路径（m*n），我们将它写在下图的第一行，之后对于m个维度中的每一个，比如说i：
  • 然后按照第一行第i列的数字，找到DCRC格子里对应维度的值范围，将写进这个范围。
• 所有序列都这样做之后，DCRC就建成了。

• 建成之后，我们还可以再随便找一个满足ACM-关系的路径r，如下图，根据各维度对应的值，在各维度都取出一个值范围，就构成了一个m维空间的超矩形。

  
  
  

  image.png
• 【编者注：如果单看某一列，格子中几个矩形范围的并集，就是数据库中序列在这个维度的值范围】

4 Time series indexing with DCRC

4.1 DCRC-based DTW lower bound (LB_DCRC)

给定一个DCRC结构之后，可以和一个query算出下界距离。这个下界距离，形式上，就是对于任意一个属于这个DCRC结构内的时间序列和query的最短距离。

• 如果要遍历可能的每一个序列，那这个是指数级的。
• 作者用动态规划，实现了一个的一个算法。是DTW容许的动态宽度比例。

4.2 Hierarchical DCRC (HDCRC)

总的来说，HDCRC就是建了一颗R-tree，基于DCRC的范围表示。每个节点对应一个DCRC结构，也对应一个参考序列r。插入以扩展区域最小为优，分裂也以最终区域面积最小为优。

image.png