Online Segmentation of Time Series Based on Polynomial Least-Squares Approximations
Authors:
- 18 March 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 32 (12) , 2232-2245
Abstract
The paper presents SwiftSeg, a novel technique for online time series segmentation and piecewise polynomial representation. The segmentation approach is based on a least-squares approximation of time series in sliding and/or growing time windows utilizing a basis of orthogonal polynomials. This allows the definition of fast update steps for the approximating polynomial, where the computational effort depends only on the degree of the approximating polynomial and not on the length of the time window. The coefficients of the orthogonal expansion of the approximating polynomial-obtained by means of the update steps-can be interpreted as optimal (in the least-squares sense) estimators for average, slope, curvature, change of curvature, etc., of the signal in the time window considered. These coefficients, as well as the approximation error, may be used in a very intuitive way to define segmentation criteria. The properties of SwiftSeg are evaluated by means of some artificial and real benchmark time series. It is compared to three different offline and online techniques to assess its accuracy and runtime. It is shown that SwiftSeg-which is suitable for many data streaming applications-offers high accuracy at very low computational costs.Keywords
This publication has 32 references indexed in Scilit:
- Querying and mining of time series dataProceedings of the VLDB Endowment, 2008
- Gesture spotting with body-worn inertial sensors to detect user activitiesPattern Recognition, 2008
- A Better Alternative to Piecewise Linear Time Series Segmentation2007
- SEGMENTING TIME SERIES: A SURVEY AND NOVEL APPROACH2004
- Real-Time Segmenting Time Series Data2003
- PhysioBank, PhysioToolkit, and PhysioNetCirculation, 2000
- On Discrete Polynomial Least-Squares Approximation in Moving Time Windows1999
- ECG segmentation using time-warping1997
- Updating and Downdating of Orthogonal Polynomials with Data Fitting ApplicationsSIAM Journal on Matrix Analysis and Applications, 1991
- On the approximation of curves by line segments using dynamic programmingCommunications of the ACM, 1961