Maximum error-bounded Piecewise Linear Representation for online stream approximation

Qing Xie, Chaoyi Pang, Xiaofang Zhou, Xiangliang Zhang, Ke Deng

Research output: Contribution to journalArticlepeer-review

62 Scopus citations


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

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: This research is partially supported by Natural Science Foundation of China (Grant No. 61232006) and the Australian Research Council (Grant No. DP140103171 and DP130103051).

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems


Dive into the research topics of 'Maximum error-bounded Piecewise Linear Representation for online stream approximation'. Together they form a unique fingerprint.

Cite this