An online PLA algorithm with maximum error bound for generating optimal mixed-segments

摘要

Abstract Piecewise Linear Approximation (PLA) is an effective method used to represent and compress a time series. It divides a time series into a number of segments, each of which is approximated by a straight line. This division and approximation is done under a metric enforcing optimized storage and compressed data quality criteria. In this article, we propose a new optimal linear-time PLA algorithm (SemiMixedAlg) for generating a set of mixed-connected (continue and disconnected segments) with guaranteed maximum error and minimized storage. An efficient “k-length” strategy is designed to determine the location of mixed segments in order to minimize the storage of mixed-connected segments. Our experiments on 43 real-world data sets show that SemiMixedAlg achieves exactly the same results as that of PipeMixedAlg (Luo et al. in Piecewise linear approximation of streaming time series data with max-error guarantees. In: IEEE international conference on data engineering, pp 173—184); the only state of the art algorithm, but with much lower time and memory costs.