An extensive experimental study on segmenting online time series with error bound guarantee
- PDF / 724,453 Bytes
- 4 Pages / 595.276 x 790.866 pts Page_size
- 61 Downloads / 183 Views
ORIGINAL ARTICLE
An extensive experimental study on segmenting online time series with error bound guarantee Ruiying Liu1 • Lijun Wang2 • Xueyan Guo3,4 • Huanyu Zhao3,4
Received: 20 March 2015 / Accepted: 19 May 2015 Ó Springer-Verlag Berlin Heidelberg 2015
Abstract An improved algorithm, i.e., HFSW, for segmenting online time series with error bound is proposed in our latest paper (IJMLC doi:10.1007/s13042-014-0310-9, 2014). Some researchers engaged in this filed read this paper and point out that there are two another existing strategies named FSW (IEEE TKDE doi:10.1109/TKDE. 2008.29, 2008) and DisAlg (VLDBJ doi:10.1007/s00778014-0355-0, 2014) which can also deal with the segmentation of online time series. And then, they want us to conduct some further experiments to demonstrate the effectiveness of our proposed method through comparing HFSW with FSW and DisAlg. Thus, we conduct such experimental comparison by testing 43 real datasets with the same fixed setting and further give the analysis to main difference among these algorithms. Keywords Time series Piecewise linear approximation Error bound
& Huanyu Zhao [email protected]
1 Introduction Recently, segmenting online time series with error bound guarantee has been proposed, and some interesting results have been gained. These algorithms can be classified two cases: connected lines and disconnected lines. For the connected one, Liu et al. [1] firstly present an algorithm called FSW. It initials from one point, and narrows the feasible space with new data point coming. When the feasible space becomes empty, a new segment is constructed. Qi et al. [2] extend FS to the polynomial functions and process multidimensional data. For the disconnected one, Xie et al. [3] give an optimal algorithm (denoted by DisAlg in this paper), which is designed by maximizing the local segments. Furthermore, another strategy (denoted by Alg) to segment connected lines is discussed in the paper. In Zhao et al. paper [4], the authors analyze the characteristic of FSW and DisAlg, and hybrid the two method to propose an algorithm (denoted by HFSW in this paper) with linear time complexity. In general, the number of segments by HFSW is less than the one by FSW. Lately, we received some issues from researchers who read our work to tell us there is another strategy for segmenting time serials with error bound guarantee. So in this paper, we clear them by conducting experimental comparison with FSW, HFSW and Alg for the number of segments.
1
Faculty of Science, Agricultural University of Hebei, Baoding 071001, China
2 Comparison
2
Ocean College of Hebei Agricultural University, Qinhuangdao 066003, China
3
SJZ JKSS Technology Co. Ltd, Shijiazhuang, China
4
Institute of Applied Mathematics, Hebei Academy of Sciences, Shijiazhuang, China
For a time series, as Fig. 1 shows, FSW starts from p1 and initials the feasible space by l1 and u1 . When p2 comes, construct the l2 ; u2 and update the feasible space to l2 and u1 . Do the same step utile the feasible space becomes empty, and
Data Loading...
