2022EDBT-(SAPLA表示法)An Indexable

2022-04-02 本文已影响0人 Caucher

标题：一个可索引的时间序列降维方法，用于最大差异缩减和相似性搜索

这个Maximum deviation的意思是：在对时间序列降维表示之后，利用这个表示重建时间序列和原始时间序列的最大差异。
如下图，蓝×是重建后的序列，黑○是原始序列，在所有时刻中，二者最大的difference就是maximum deviation.

image.png

编者的总结

本文提了一个叫SAPLA的时间序列表示，基于动态分段PLA的，相比于之前的APLA，复杂度上有一个数量级的提升，精度上相差不多。
SAPLA的实现是一个迭代的过程。迭代通过不断调整各个分段的长度，位置，想要达成的目标是在所有分段的总最大差异最小。
效率提升的一个重要原因就是，改变分段长度（像合并两个段，分裂某个段，延伸1个点）这样的操作，可以让对应分段的PLA以O(1)的复杂度内做调整（但是error bound $\epsilon$ 不可以，所以需要用其上界 $\beta$ 来代替， $\beta$ 就是最大差异，也可以在O(1)复杂度内做调整）。
通过对齐分段，给出了基于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，但复杂度高达 $O(Nn^2)$ ，n是时间序列长度，N是分段数。
- APLA也有问题。APLA只最小化一个段的最大差异，而非所有最大差异的和。
作者对APLA进行改进，改为自适应长度的，称为SAPLA，好处是快的多，复杂度为 $O(n(N+logn))$

2 RELATED WORK

PLA：分段线性表示。
- 等长固定段数，因此精度有限；
- 复杂度O(n)
APLA：自适应的分段表示
APCA：自适应段长度，每段常量表示。
PAALM：基于PAA和拉格朗日因子，复杂度O(n)，并不关注与最大差异
CHEBY：用切比雪夫不等式系数来做近似。复杂度O（nN）。维数不能高于25.

3 PRELIMINARIES

$\epsilon_i$ 表示第i段的最大差异。
$\beta_i$ 表示第i段的最大差异和的上界。 $\beta$ 是所有段最大差异之和的上界。

4 SELF ADAPTIVE PIECEWISE LINEARAPPROXIMATION (𝑆𝐴𝑃𝐿𝐴)

SAPLA的设计目标是降低 $\beta$ 。主要方式是寻找段的端点。
基本做法是把 $\beta_i$ 最大的拆分成两段， $\beta_i$ 较小的区域合并。
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段的 $\beta_i$ 可以这样计算：找到在该段起点，终点，延伸点上，原始segment，Extended Segment, Increment Segment （两线一序列）的两两最大差异，每个位置有三个difference，三个位置共9个，选出其中最大的，再乘上新段长度-1。

可以证明， $\beta_i$ 在正常情况下，是 $\epsilon_i$ 的上界。

4.1.3 Reconstruction Area

相邻两段也可以O（1）时间内重新计算PLA，生成重建区域。称为合并操作。

image.png

4.1.4 (𝛽𝑖) Segment Upper Bound in Merge Operation

生成新段的 $\beta_i$ 的计算方式，是在四个端点的位置上（如上图四点），找原始序列，原始重建序列，合并重建序列的两两最大差异，然后乘上新段的长度-1

4.2 Initialization

初始化过程由用户给定段数N，要遍历一次一整条序列，产生至少N个段。
基本原则是选择Increment Arae最大的N个段，由一个堆保存。

具体过程如下：

首先是第一个段，就是前两个点构成的PLA表示，可以进堆；
之后到了第三个和第四个点构成的第二段，需要检验是否可以进堆（算Increment Area的面积）：
- 如果可以，则进堆，同时要和前面的段算一下merge的情况，然后保存下来，后面过程会用。进堆后，开始寻找第三段。
- 如果不可以，那么把此段继续延长。

4.3 Split & Merge Iteration

分裂操作是merge的反操作；
每次分裂选择 $\beta_i$ 最大的那一段，分裂的点选择在有最大重建区域的位点上，采取peak finding技术【编者注：类似于梯度下降的贪婪算法】。

image.png
分裂后还是能用O(1)时间内算出两段 $\beta_i$ 。

整体流程：

整体来说，当段数小于N时，会找重建区域最大的位置做分裂；段数大于N时，会找重建区域最小的相邻两段做合并。
当段数等于N时，先找重建区域最大的做一次分裂，然后再找重建区域最小的做一次合并，得到一个新的全序列上界 $\beta^{sm}$ 。同理，可以先合并，再分裂，得到一个 $\beta^{ms}$ 。如果当前的 $\beta$ 比这两个都小，那么算法就收敛了。进入到下一步，否则根据更小的那个操作，重新迭代。

【编者注：这里堆中内容到底是重建区域还是 $\beta$ 视情况而定。 $\beta$ 是重建区域面积的上界，所以如果可以顺便算出面积，就使用面积，否则用 $\beta$ 来代替】

4.4 Segment Endpoint Movement Iteration

找具有最大 $\beta_i$ 的那个段，试图移动它的两个端点做进一步调优。
基本做法和前面的思路也是类似的，向左右前进或后退，使得全序列的 $\beta$ 会有变化，不断在相邻段之间尝试，至少取得每两个相邻段之间的局部最优。

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

2022EDBT-(SAPLA表示法)An Indexable

编者的总结

编者的思考

ABSTRACT

1 INTRODUCTION

1.1 Motivation

2 RELATED WORK

3 PRELIMINARIES

4 SELF ADAPTIVE PIECEWISE LINEARAPPROXIMATION (𝑆𝐴𝑃𝐿𝐴)

4.1 Proposed Equations and Area Computation

4.1.1 Increment Area.

4.1.2 (𝛽𝑖) Segment Upper Bound in Initialization

4.1.3 Reconstruction Area

4.1.4 (𝛽𝑖) Segment Upper Bound in Merge Operation

4.2 Initialization

4.3 Split & Merge Iteration

4.4 Segment Endpoint Movement Iteration

5 INDEXING USING A LOWER BOUNDING DISTANCE MEASURE

5.1 Lower Bound Distance Measure for Adaptive-Length Segment Dimensionality Reduction Method

5.2 Distance Based Covering with Convex Hull (DBCH structure)

6 EXPERIMENTAL EVALUATION

猜你喜欢

热点阅读