编者的思考：
-
time window的时间段是用户来定义的，据文中意思，应该是把整个时间序列均分成若干段的，而实际的time window未必是明显的平均的段划分，至少未必是用户定义的平均的段划分，这里至少有改进的空间，比如提供一种自适应性来适应时间段的划分；
-
由于时间序列节点之间的距离是由极值来衡量的，所以一旦出现异常点，即使原来有强相关，也不会被加入到同一个cluster里。也许可以考虑每个window每个序列加一个异常点队列？
-
还是距离判断的问题，这里是将同一个window的每个序列的平均值都移到0点，然后计算两个序列值的差的最大值，这里有一个漏洞：就是绝对值的问题，比如某公司每支股票价格和公司职员人数的两个序列，价格可能是在0~5这样一个范围，人数可能是几千，即使都减去平均值，绝对差也不能很好地代表这两个序列之间的关系。也许和序列绝对值的相对差异更能描述两个序列变化趋势的相似性。
如果引入更为精确的距离判断，势必带来解压时更大的时间开销，也就是基序列、偏移和解压的算法会更复杂，而非线性相加
Abstract
文章的主要目的是解决多时间序列的存储压缩问题。
- 提出了一个代表模型，用一个基序列和一个单值来代表其它序列
- 提出了两个图论算法用于将时间序列聚簇，
有高压缩率，
牺牲一些压缩率，达到高性能。
1. Introduction
-
SBR
最开始有一个叫SBR的机制，可以将相似的时间序列聚集成簇，在同一个簇内，用一个基础序列估算其它序列。局限有两个地方：
- 只能在运行算法之前，将相似的序列静态的绑在一起，这对于长时间序列来说不合适
- 误差范围是
而非
这意味着单时间点的误差范围不可预测
-
GAMPS
误差范围可以控制在
-
MTSC（本文）
空间消耗极小，核心的是一个分组策略，这个策略能保证组数尽可能少，
2. Preliminaries
误差以所有序列中最大偏差那个计算
2.1 APCA简介
将一个时间序列划分成k段，每一段保留一个值，这个值和这个段的所有value的差在有限的范围内
3. 压缩模型和算法概览
3.1 表示法模型
单视窗模型
一个多时间序列集S，可以被表示成一个三元组
- C把S划分为多个序列簇
- B为每个序列簇找到一个基序列
- 某个簇中的任一序列可以表示为该簇的基序列加上一个偏移量，这就是说对每一个S中的序列，都有一个相对于其簇中基序列的偏移量，所以这个O的基数等于S的基数
到此为止，可以单独表示一个S，现在的目标是尽可能减少S和B的基数（是同一个量，即划分成多少个序列簇）。
多视窗模型
按照时间段再把时间分开，形成不同时间段的多序列集，代表在第i个时间段，第j个序列。每个多序列集
可以被一个
唯一表示，那么我们的表示模型可以理解为
注意：视窗长度，即时间段长度，是<u>用户自定义</u>的。
3.2 理论基础
定义1：
- 两个序列是
引理1：
- 对于一个时间如果任意一个时间序列集，如果任意两个序列之间都是
的，那么这个时间序列集就有一个基序列B，和所有集合中的序列的最大误差是
在图论算法中，将每个时间序列视为一个顶点，将两个序列之间的相似度视为边。
4. 算法
4.1 序列分组策略
Mc-grouping
对于一个window里面的所有子序列，先都减去他们的平均值，这样让每个子序列在给定属性下的平均值是0。注意此时不同子序列减去的平均值肯定不一样，但是由于我们关注的是子序列的变化趋势是否相同，绝对值意义不大，所以把“偏移量”减去会方便计算。
每个点代表一个正规化后的子序列，边代表新子序列的‘距离’，即在这个window下的最大差值，只有距离小于的才能成为一条边。
在每个window都做好一幅图之后，可以用一个基于的算法聚集序列。
定义2：
在一幅图里的最大完全子图。
找这个是一个NP-Hard问题，没有精确算法，这里采用一个快速确定性算法。
先找到一个最大完全子图作为第一个cluster，然后删去这个cluster的所有点和边，在剩余的图中找下一个，直到没有边，剩下的点作为单点cluster.
Inc-grouping
主要是利用连续的window之间联系的相似性，先从上一个window继承它的cluster，然后再根据自己window的情况修改修改。
- 首先正规化，然后构图
- 之后对于上一个window的第一个cluster，继承它的所有点，它的边如果在本window有就画上。
- 如果做出来的cluster是个完全图，就直接变成这个window的cluster，如果不是完全图，就删去一些点让它是完全图。
- 首选度数最小的点
- 删点循环
- 如果最后都变成一个个单点了，那也构成单独的cluster
- 对于上一个window的每一个cluster都执行此操作，最惨的就是都变成单点了，然后进行下一步。
- 下一步就是把单点试探着加入所有的cluster，能加就加，不能加就算了。
一起使用
第一个window，肯定用mc-grouping；对于之后的window
- 用边的变化率来衡量它和第一个window的图有多大差别
- 如果差别未超过<u>用户定义的上界</u>，就用inc-grouping
- 否则用mc-grouping
4.2 基序列和偏移量
现在要计算某个window里面cluster的基序列。
把一个window里的time分成若干段，每一段保留一个右端点，然后保留一个该段的代表值。
这个分段可以按时间向前推进：
- 初始化时间为1，扫所有的序列时间为1的点，找到最大值和最小值
- 往下推进一个单位时间，再扫所有序列，找极值，如果和上一个段的极值合起来还满足误差要求，就合起来，否则新成立一个段。
至于某个window的序列集来说，我们把序列集中的每个序列的平均值作为这个序列在这个window下的offset，也就是说每个window，都有序列个数那么多个offset。
至于序列集中只有一个序列的单点来说，就是用APCA表示法，把它作为一个基础序列。此时偏移量为0，因为没有一个正规化的过程让他移动到平均值为0的位置，也没必要，因为无需和其它序列共享一个基序列。
基序列和偏移量可以将一个window的所有序列以的误差复盘回去。
5. 算法
这个算法和算法唯一的差别就是分组策略。
找cluster是通过最大完全子图这个算法，这里用的是另一种算法。
定义3：星形子图
存在一个顶点，使得所有其他顶点都和他有边
引理3：的子图是一个的一个图
星形子图（cluster)选取算法：O(N)
- 首先选一个度数最高的顶点，用它和所有直接和它相连的点构成第一个cluster
- 在原图中删掉这个cluster，然后重复上面的步骤，直到没有边
总结
本文的目的就是对多个序列存储进行压缩存储，压缩存储有精度损失
将时间序列按固定的时间段分成若干window,在每个window中先去找groups，然后对每个group里面找到一个基序列，然后group里每个序列都有一个offset.
group方法文中提出两种：
先找一个最大完全子图，然后删去，递归的去找，直到最后图中没有边。
先从度数最大的点开始找星形子图，然后删去，递归的去找，直到图中最后没有边。
基序列找法：
从时间起点开始，找连续时间段内所有序列的极值之差，直到到某个时刻，极值之差超过，那么这一时段就是一个Seg，极值的平均值就是这一段的base值。依次方法，把整个window分成若干不均匀时间段，每个时间段都有一个base值。
偏移量确定：
就是某一序列在某一window下的平均值。
解压时只需要将相应base值加上offset，就是该段的复盘值，误差在以内。
网友评论