Indexable online time series segmentation with error bound guarantee
Indexable online time series segmentation with error bound guarantee
复制标题
DOI：
10.1007/s11280-013-0256-y
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Jianzhong Qi;Rui Zhang;K. Ramamohanarao;Hongzhi Wang;Zeyi Wen;Dan Wu
中科院分区：
文献类型：
--
作者：
Jianzhong Qi;Rui Zhang;K. Ramamohanarao;Hongzhi Wang;Zeyi Wen;Dan Wu
在各种应用中，时间序列流数据量迅速增长。为了降低时间序列数据的存储、传输和处理成本，常用的方法是分段逼近。在本文中，我们提出了一种新的在线分割算法，近似时间序列的一组不同类型的候选函数（不同阶的多项式，指数函数等）。并且随着时间序列的模式改变而自适应地选择最紧凑的一个。我们称这种算法为自适应近似（AA）算法。AA算法逐步缩小系数坐标系中候选函数的可行系数空间（FCS），使每个数据点上的误差范围尽可能长。我们提出了一种算法称为FCS算法的可行系数空间的增量计算。我们进一步提出了一个映射为基础的索引相似性搜索的近似时间序列。实验结果表明，我们的AA算法产生更紧凑的近似的时间序列比国家的最先进的算法具有较低的平均误差，我们的索引方法处理近似的时间序列有效的相似性搜索。
The volume of time series stream data grows rapidly in various applications. To reduce the storage, transmission and processing costs of time series data, segmentation and approximation is a common approach. In this paper, we propose a novel online segmentation algorithm that approximates time series by a set of different types of candidate functions (polynomials of different orders, exponential functions, etc.) and adaptively chooses the most compact one as the pattern of the time series changes. We call this algorithm the Adaptive Approximation (AA) algorithm. The AA algorithm incrementally narrows the feasible coefficient spaces (FCS) of candidate functions in coefficient coordinate systems to make each segment as long as possible given an error bound on each data point. We propose an algorithm called the FCS algorithm for the incremental computation of the feasible coefficient spaces. We further propose a mapping based index for similarity searches on the approximated time series. Experimental results show that our AA algorithm generates more compact approximations of the time series with lower average errors than the state-of-the-art algorithm, and our indexing method processes similarity searches on the approximated time series efficiently.