标题：通过跨范围限定进办法态覆盖构建的时间序列索引
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.
- 有了ACM关系之后，我们就可以度量两个不等长序列的隔断。
- 具体来说，要找到一个ACM-关系r，使得用r将短序列延伸后，和长序列的欧式隔断最小。
- 这个延展后的欧式隔断就是新度量D，关系r就是对应的ACM关系。
3.3 Approximate subsequence
ACM关系可以用于将短序列延展伸长，本节讲的近似子序列AS，可以用于将长序列变短。
根本方法就是分段做均值。标题是怎样分段？
- 给出一个目标函数：变短后的序列和原始序列的D最小。
- 至于具体怎么找分段，粗暴的方式就是遍历全部排列组合，分别盘算D。也可以用动态规划淘汰搜刮空间。
3.4 Covering set
这一节讲怎样使用DCRC来聚集时间序列。
<ul>使用DCRC必要一个参考序列c，它的维度是比较低的，设为n。数据库里的时间序列长度较长，可以设为m。
- 理论上参考序列越中央越好，现实环境c是数据库里恣意选的序列，通过AS方法紧缩之后成为的c。
之后对于数据库里的每一条序列ts，去找和c的最优ACM-关系r。
DCRC如下图，m个维度，每个都有一个本身的格子，每个格子内里包罗真实序列的范围（可能来自周边的多个维度，由于DTW的动态范围）。
- 举个例子，中央第三列，体现DCRC的第三个维度，包罗真实数据会合序列第二个维度的范围，和第三个维度的范围。
刚才我们算出了ts和c的最优ACM关系r，它就是一条DTW路径（m*n），我们将它写在下图的第一行，之后对于m个维度中的每一个，比如说i：<ul>
然后按照第一行第i列的数字，找到DCRC格子里对应维度的值范围，将 |
