Maximum error-bounded Piecewise Linear Representation for online stream approximation

摘要: Given a time series data stream, the generation of error-bounded Piecewise Linear Representation (error-bounded PLR) is to construct number consecutive line segments approximate such that approximation error does not exceed prescribed bound. In this work, we consider bound in $$L_\infty $$ L ? norm as criterion, which constrains on each corresponding point, and aim designing algorithms generate minimal segments. literature, optimal are effectively designed based transformed space other than time-value space, while desirable solutions original domain (i.e., space) still lacked. article, proposed two linear-time PLR for stream domain, named OptimalPLR GreedyPLR, respectively. The an algorithm generates approximation, GreedyPLR alternative solution requirements high efficiency resource-constrained environment. order evaluate superiority OptimalPLR, theoretically analyzed compared with state-of-art also achieves linear complexity. We successfully proved theoretical equivalence between discovered processing practice. extensive results empirical evaluation support demonstrate effectiveness our algorithms.