DS-TREE
标题：一个数据自适应的和动态的分段索引，用于time series的全量匹配

编者的问题

1. 首先是对树做插入的时候，由于每个节点在每个segment上都有一定的上下界范围Z，未必能cover掉全部的值域，这时如何插入？根节点反向分裂么？

编者的思考

1. 本文的实验用的还是大量小序列来进行的，从设计思路上来看，长序列也许也可以用同样的方法来构造，不知道效果怎么样？
2. 从大小上来看，短序列的索引大小已经在几十MB的范围内，那么长序列恐怕要做基于磁盘的索引，此时本文的二叉结构就不再适用了，应考虑改变分割方式，做成扁平的树结构，以实现基于磁盘的索引。
3. 作者提到本文的方法对于不等长的subsequence query可以直接使用，原因在于当时2013年，不等长的subsequence query主要利用滑动窗口，拆分成等长的再拼接。而最近的19年ULISSE文章是基于iSAX做的不等长query，已经不再是等长拼接技术，在这方面DS-Tree能否有用武之地？

ABSTRACT

本文考虑similarity search问题。SAX,iSAX都是将时间序列等分，本文发现这会造成大量的时间空间浪费，因此本文提出了一个数据自适应的和动态的分段索引。
除此之外，本文还能为time series之间的距离提供一个比较紧的上下界。

1. INTRODUCTION

whole matching是similarity search的一个子问题，专门处理ED距离下，等长time series的情况。
对于这个问题，有很多索引结构被提出，其无外乎以下两种思路：

Principle1：基于全局分段的维度削减

一个time series可以被表示为高维空间的一个点，首先对time series的维度进行抽象整合，进一步在低维空间中建立R-tree进行索引，例如iSAX。
然而这些降维方法都是数据无关的，基本上是直接等分的全局方法，如果能够根据数据本身进行有意义的切割，能够将维度降到更低。

Principle 2: Using Lower Bounds in Search

whole matching中的representation很重要一个性质就是距离下界性，经过表示的距离肯定比真实距离要小，这种性质安全之处在于不会出现假阴性，只要表示后的距离比大，那么真实距离肯定也很大，就不用考虑了。
下界被应用较为广泛，但是上界缺没被应用过。上界的优点在于，如果表示后的距离比小，那么真实距离肯定也小，都不用具体去计算了。

本文基于的表示扩展了APCA，支持分段和数据自适应，还利用了上界。

2. EXTENDING APCA REPRESENTATION

本文提出的表示叫EAPCA。

2.1 APCA

APCA就是能提供距离下界计算的一种表示。
APCA是把time series分段，一致但未必等长，每段保留终点和均值进行表示，可以证明能提供距离下界。

image.png

2.2 EAPCA and Upper/Lower Bounds Using Standard Deviations

EAPCA只是简单的将APCA的每个分段扩展一个标准差。因此扩展除了更紧致的上界和下界。

image.png

2.3 Bounding Distances to a Set of Time Series

两个序列之间的距离可以提供上下界，一个序列和一个序列集合之间的距离，一样可以提供上下界。

image.png

image.png

3. THE DSTREE INDEX

3.1 DSTree

首先是refinement的定义，把一个分段区间更细致的进行分割，称为refinement。

image.png

子节点要么是父节点的一次refinement，要么和父节点一样。
每个节点包含以下内容：

• 有多少序列在这里被索引
• SG，分段
• 各个分段的均值和标准差的极值
• 叶子节点直接指向磁盘文件的time series，有一定capacity
• 内部节点记录一些分割策略

3.2 DSTree Construction

初始化就是完全不分割的根节点。
插入算法主要依赖于两个函数，假设插入序列X，一个是找到序列X最合适的叶子节点；另一个是找到最优的分裂方法。
如果找到叶子节点，承载未满，直接插入即可；如果满了，那就要分裂，把原节点的内容全部分裂到两个新子节点去。

3.3 Node Splitting Strategies

3.3.1 ideas

分割分两种，一种是横向分割，一种是纵向分割。横向分割不动segmentation，只是把其中的序列分成两部分，基于均值或者方差；纵向分割会refinement segmentation.

image.png

3.3.2 Splitting Strategies

• H-split 就是选择一个小的segment为基准，从原有的均值/标准差范围从中间劈开两半，尝试分裂。
• V-split 也选择一个小segment为基准，从中间劈开两半进行分段，从两个小段中任选一段，以H-split的方法进行分裂

这样，分割策略可以由：

1. 选择的Segment id
2. 划分策略
3. 均值/标准差
   三元组来构成。

3.3.3 Splitting Strategy Quality Measure

image.png

最终结果如图示，也就是说，在每个segment内，均值的极差要求越小越好，方差的最大值要求越小越好。
推导过程略，主要是对于任一个query和一个节点的所有序列的均值和标准差的上下界构成的范围，要越小越好，找到一个通用的上界表示，就构成了该结论。

3.3.4 Finding Splitting Strategies

image.png

基于Qos，可以定义一个分裂收益，计算所有3分割方法，分别计算收益，选择最大的即可。这样分割方法就找到了。
还有一个是找到插入序列X对应叶子节点N的方法，首先按照N的分段方式进行分段，再根据其分裂方式进行递归下降查找。

3.4 Analysis of DSTree

• Adaptive segmentation
• Data distribution：DS Tree没有假定任何特殊的数据分布
• Balance of DSTree：DS-Tree和iSAX都会造成倾斜，iSAX更严重。DS-Tree的形状和输入序列顺序相关，可以重新排列几次，选最优的。

4. QUERY ANSWERING ALGORITHMS

4.1 Similarity Search

4.1.1 A Heuristic Method

就像插入一样去查找，找到的是一个近似结果。

4.1.2 The Exact Search

精确查找是和传统思路类似。首先初始化一个BSF answer，就用启发式方法找一个近似的，以削减搜索空间。之后定义一个优先级队列，按照下界进行排序。首先入队根节点，之后遍历整棵树就可以了。

4.2 Distance Distribution Histogram

对于所有叶子节点计算上下界，然后进行计数，绘制直方图。不详说。

5. EMPIRICAL EVALUATION

效率上，扩展性上，空间占用上比iSAX略好一些，近似结果的质量，索引平衡性上尤其比iSAX要好。