标题：TS-树：高效时间序列搜索和检索

编者的总结

1. 本文基于SAX表示，对所有时间序列的SAX表示排了一个序。排序的方法也很简单，就是按照维度从前到后，字母表的自然顺序进行排序，由此构建了B树。
2. 在排序的基础上，为叶子节点中的序列，做了个MBR，MBR和排序组合起来进行下界剪枝。但是MBR的作用有多大暂不清楚。

编者的思考

1. 下界距离给的太模糊了，一方面确实也不好从理论上给出设计，想必这也是该文没有复现代码，影响力较弱的原因之一。

4. THE TS-TREE

TS-tree采取了B树的结构，做成一颗平衡树。同时也吸取了R树的特征，在树的叶子节点存了上界和下界信息。既然是B树，自然需要序列之间可以排序，下面首先介绍排序方式：

• 排序：两个序列a和b，a<=b当且仅当以下两个条件满足其一：
  • a比b短，且完整的a和b的前缀完全一致；
  • a和b有一段共同前缀，然后在接下来的位置，a比b要小。

基于排序，我们可以进一步提供分隔符将两个序列分割开：

• 分隔符：在大小介于两个序列之间的，长度最短的序列。

  
  image.png
  • 从图中我们可以看出，由于共同前缀的序列没那么多，所以分割符的长度通常很短，很多甚至只有1个数。

在同一个节点内部，TS-tree通过量化的方式进行组织：

• 量化：首先将有理数值域分成若干个区间，每个区间用符号代替，这样时间序列可以替换为相应的等长的符号序列，称为量化。

常用的量化方式有两种：

• 等宽量化：也就是将值域均匀分割；
• 等深量化：将值域做分割，使得在每个区间的数据量大致一样。（SAX趋向于这种量化方式，因为做了正态分布的分割）

通过量化，相似的序列数据得以组织在一起，同时分隔符相应也会更长，提供更多信息用来分割，对应于图1，量化之后，形成树的模型如下图：

image.png

• 除了量化的分隔符，TS-tree中仍有对每个叶子节点的信息抽象，称为元数据，其实就是量化后的MBR。

  
  image.png

• 维度压缩：按照上述的想法，看起来每个维度都要单独量化，那对于索引大小来说是不可能的，维度必须首先经过压缩。压缩备选算法有：PAA/DWT/PCA.

5. QUERY PROCESSING IN TS-TREES

5.1 TS-tree mindist

TS-tree也是存在着下界距离剪枝的。下界距离由两部分构成，一部分是元数据提供的下界，另一部分是分割符提供的下界。二者取交集，将得到最终的下界。
如下图：元数据提供了实现部分的数据范围，分割符提供了虚线部分的数据范围（开范围），两个数据范围取交集，则得到最终的灰色阴影数据范围。

image.png

5.1.1 元数据下界

元数据就是一个MBR，因此下界也非常好定义，如下式：

image.png

图例如下，在各个维度上找和MBR的距离，然后2范数相加。

image.png

5.1.2 分割符下界

分割符的下界不能逐维度的去计算下界距离，因为分割符的各个维度之间是有顺序的，各个维度之间并非是独立的。
【编者：我认为本文在这一部分下界的公式理论还不够完备，存在不少疏漏，因此这里只对下界做示意说明，不放详细公式】

• 一个子树的两个分割符，大部分情况只能勾画出一个开放的区域。
  • 只有最后一个维度不同的分割符，才可能导致闭合区域，此种情况直接参考5.1.1的MBR下界即可。
• 对于开放区域：如果query在开放区域内，那下界为0，直接取5.1.1MBR的下界即可；小于区域左侧分割符的，和大于区域右侧分割符的，有几个距离可能构成一个下界距离，我们需要在其中取最小的，作为下界距离。为了描述方便，我们只以小于区域左侧分割符的query为例，另一侧取对称即可：

  1. 和左侧分割符的距离可能成为下界距离；

     
     image.png

  2. 顺序的将维度遍历，和某一维的距离(+1)可能成为下界距离，但是下面这种情况此条则不适用：

     
     image.png
     • +1要视情况而定，关键看query的的下一个维度是否比左侧分割符的该维度要大。
     • 一旦分割符的下界距离在此处停止之后，后面的维度可以用MBR下界距离来放大下界。

总的来说，是结合了分割符和MBR的下界距离：

image.png

5.2 Extension to DTW

将MBR简单扩展一下即可。

5.3 Multistep query processing

其实就是R-tree的branch-and-bound策略，按照插入的方式去查询。注意的是，query也需要首先降维（量化），然后进行下界距离计算。

6. EXPERIMENTS

实验部分由于该文年代过早，比较方法没有意义，因此省略了。