标题：一个可索引的时间序列降维方法，用于最大差异缩减和相似性搜索
这个Maximum deviation的意思是：在对时间序列降维表示之后，利用这个表示重建时间序列和原始时间序列的最大差异。
如下图，蓝×是重建后的序列，黑○是原始序列，在所有时刻中，二者最大的difference就是maximum deviation.
image.png
编者的总结
- 本文提了一个叫SAPLA的时间序列表示，基于动态分段PLA的，相比于之前的APLA，复杂度上有一个数量级的提升，精度上相差不多。
- SAPLA的实现是一个迭代的过程。迭代通过不断调整各个分段的长度，位置，想要达成的目标是在所有分段的总最大差异最小。
- 效率提升的一个重要原因就是，改变分段长度（像合并两个段，分裂某个段，延伸1个点）这样的操作，可以让对应分段的PLA以O(1)的复杂度内做调整（但是error bound
不可以，所以需要用其上界
来代替，
- 通过对齐分段，给出了基于PLA的动态分段技术的下界距离，可用于构造索引；
- 将原来基于MBR的R-tree索引，改成了基于凸包的DBCH索引，效率上有所提升。
编者的思考
- 从实验中来看，SAX的最大差异很大，但是剪枝率和精确性的效果都很好，这和本文最初的motivation是矛盾的。需要一个特别的解释。
作者在印证max deviation有利于剪枝时，主要是用之前的论文背书，主要就是一些动态分段的方法。从实验中看，在这些方法上，这个结论没问题。但是在SAX上却反过来。这让编者产生了对max deviation这一指标重要性的质疑。而max deviation是SAPLA的优化目标。 - DBCH树和其它没有overlap的索引树相比情况如何呢？比如基于APCA的DS-tree，基于SAX的iSAX。既然DBCH的motivation是R-tree有overlapping，那就需要和无overlap的树也比一比，哪怕结果是各有优劣。
ABSTRACT
- 时间序列降维是必须的。
- 一些方法牺牲最大差异来换取速度。
- APLA(Adaptive piecewise linear approximation)最大差异最好，但是很慢。
- 本文提出了SAPLA(Self Adaptive piecewise linear approximation)
- 包含三步，初始化，分裂&合并，段端点移动
- 比APLA快n倍，n是时间序列长度， 最大差异的损失是微小的。
1 INTRODUCTION
- 挑战：降维的同时维护重要的时间序列特征
- 本文使用欧式距离做相似性查询。
- 最大差异越小，搜索时剪枝的机会越多
1.1 Motivation
- 自适应分段降维一般很耗时，尤其对于经常性变化的时间序列。
- 典型的，APLA结合了APCA和PLA的优点，可以保证error bounds，但复杂度高达
，n是时间序列长度，N是分段数。
- APLA也有问题。APLA只最小化一个段的最大差异，而非所有最大差异的和。
- 典型的，APLA结合了APCA和PLA的优点，可以保证error bounds，但复杂度高达
- 作者对APLA进行改进，改为自适应长度的，称为SAPLA，好处是快的多，复杂度为
2 RELATED WORK
- PLA：分段线性表示。
- 等长固定段数，因此精度有限；
- 复杂度O(n)
- APLA：自适应的分段表示
- APCA：自适应段长度，每段常量表示。
- PAALM：基于PAA和拉格朗日因子，复杂度O(n)，并不关注与最大差异
- CHEBY：用切比雪夫不等式系数来做近似。复杂度O（nN）。维数不能高于25.
3 PRELIMINARIES
表示第i段的最大差异。
表示第i段的最大差异和的上界。
是所有段最大差异之和的上界。
4 SELF ADAPTIVE PIECEWISE LINEARAPPROXIMATION (𝑆𝐴𝑃𝐿𝐴)
- SAPLA的设计目标是降低
- 基本做法是把
最大的拆分成两段，
- SAPLA最后的表示是每一段的终点，斜率，截距。
4.1 Proposed Equations and Area Computation
4.1.1 Increment Area.
- Increment Segment：就是把某一个段向前延伸一个点。原来段的PLA表示，可以通过O（1）的复杂度转换成延伸段的PLA表示。
- Extended Segment：利用原先的段PLA表示，往前延伸一个点。
-
通过证明可以得到，这两个segment必然在这一段有一个交点。这样就产生两个三角形，如下图绿色部分，称为Increment Area.
image.png
4.1.2 (𝛽𝑖) Segment Upper Bound in Initialization
第i段的可以这样计算：找到在该段起点，终点，延伸点上，原始segment，Extended Segment, Increment Segment （两线一序列）的两两最大差异，每个位置有三个difference，三个位置共9个，选出其中最大的，再乘上新段长度-1。
- 可以证明，
的上界。
4.1.3 Reconstruction Area
相邻两段也可以O（1）时间内重新计算PLA，生成重建区域。称为合并操作。
image.png
4.1.4 (𝛽𝑖) Segment Upper Bound in Merge Operation
生成新段的的计算方式，是在四个端点的位置上（如上图四点），找原始序列，原始重建序列，合并重建序列的两两最大差异，然后乘上新段的长度-1
4.2 Initialization
- 初始化过程由用户给定段数N，要遍历一次一整条序列，产生至少N个段。
- 基本原则是选择Increment Arae最大的N个段，由一个堆保存。
具体过程如下：
- 首先是第一个段，就是前两个点构成的PLA表示，可以进堆；
- 之后到了第三个和第四个点构成的第二段，需要检验是否可以进堆（算Increment Area的面积）：
- 如果可以，则进堆，同时要和前面的段算一下merge的情况，然后保存下来，后面过程会用。进堆后，开始寻找第三段。
- 如果不可以，那么把此段继续延长。
4.3 Split & Merge Iteration
-
分裂操作是merge的反操作；
-
每次分裂选择
image.png
-
分裂后还是能用O(1)时间内算出两段
整体流程：
- 整体来说，当段数小于N时，会找重建区域最大的位置做分裂；段数大于N时，会找重建区域最小的相邻两段做合并。
- 当段数等于N时，先找重建区域最大的做一次分裂，然后再找重建区域最小的做一次合并，得到一个新的全序列上界
。同理，可以先合并，再分裂，得到一个
。如果当前的
【编者注：这里堆中内容到底是重建区域还是视情况而定。
是重建区域面积的上界，所以如果可以顺便算出面积，就使用面积，否则用
来代替】
4.4 Segment Endpoint Movement Iteration
找具有最大的那个段，试图移动它的两个端点做进一步调优。
基本做法和前面的思路也是类似的，向左右前进或后退，使得全序列的会有变化，不断在相邻段之间尝试，至少取得每两个相邻段之间的局部最优。
5 INDEXING USING A LOWER BOUNDING DISTANCE MEASURE
本节为所有自适应长度的表示提供了一个下界距离。
【编者注：从后文描述的来看，应该是自适应长度的基于PLA的表示，提供了一个下界距离。是否能推广至不基于PLA的，有待考证】
5.1 Lower Bound Distance Measure for Adaptive-Length Segment Dimensionality Reduction Method
- 想要建索引，肯定要有下界距离；
- 对于两个SAPLA表示中的某个段，其实和PLA是一样的，算重建距离即可，这就是这一段的下界距离；
- 问题在于如何将两个SAPLA表示各段对齐，方法也很简单， 把长的段分别截断成短的就可以了；
- 然后就可以在全序列上算下界距离。
5.2 Distance Based Covering with Convex Hull (DBCH structure)
- 之前APCA基于MBR的方法overlap很多。
- 本文方法：找到一个节点中，下界距离最大的两条序列作上下界。这个距离称为节点容量。节点内其它序列到上下界的距离都不超过容量。
- 节点分裂的时候，遍历节点中所有序列，算和上下界的近似距离。和上界近进入左节点，和下界近进入右节点。
-
这样的节点和单条序列也是有下界的。如果序列和节点上下界的距离都不超过容量，那么下界为0，该序列属于该节点。否则，选择较小的那个距离作下界距离。
image.png
6 EXPERIMENTAL EVALUATION
image.png
- 动态分段比静态分段的max deviation要更小，但是耗时也普遍更长。
-
本文方法和APLA精度差不多，但是速度要快几个数量级，印证了前面的分析。
【编者的问题：PAA要比PLA更慢，这是为什么？】
image.png
- 动态分段技术普遍精度更高；
-
DBCH的方法在3个动态分段技术上有显著优化，但是在静态分段技术上没有提升，甚至有些退化，相比于R-tree。
【编者的问题：从此图和上图来看，SAX技术似乎无论在效率还是在精度上都超过了包含在SAPLA在内的一众分段表示技术，这一点应如何看待？
另外SAX(PAA)在max deviation这一指标上并不出色，却有着更好的精确度，其中的原因在哪里？】
image.png
-
从效率上来说，DBCH树比R树有明显优化，在各种表示技术上基本都能反应出来。
image.png
网友评论