《Blazing Fast Time Series Segmentation Based on Update Techniques for Polynomial Approximations》.pdf

2013 IEEE 13th International Conference on Data Mining Workshops2013 IEEE 13th International Conference on Data Mining Workshops Blazing Fast Time Series Segmentation Based on Update Techniques for Polynomial Approximations ´ Andre Gensler, Thiemo Gruber, Bernhard Sick Intelligent Embedded Systems, University of Kassel, Germany {gensler, gruber, bsick}@uni-kassel.de Abstract—Segmentation is an important step in processing (segment boundaries), e.g., thresholds on the approximation and analyzing time series. In this article, we present an approach error (typically a least-squares error) or thresholds on the local to speed up some standard time series segmentation techniques. curvature of the approximating polynomial to segment at local Often, time series segmentation is based on piecewise polynomial optima of the time series. In most cases, a least-squares fit of approximations of the time series (including piecewise constant a time series or a certain section (window) of a time series is or linear approximations as special cases). Basically, a least- computed using a technique such as a QR decomposition and, squares fit with a polynomial has a computational complexity that depends on the number of observations, i.e., the length of the time then, the complexity of this approach depends on the number series. To improve the computational complexity of segmentation of data points (i.e., the window size). techniques we exploit the fa