Maximum error-bounded Piecewise Linear Representation for online stream approximation

Xie, Qing, Pang, Chaoyi, Zhou, Xiaofang, Zhang, Xiangliang and Deng, Ke (2014) Maximum error-bounded Piecewise Linear Representation for online stream approximation. The VLDB Journal, 23 6: 915-937. doi:10.1007/s00778-014-0355-0

Author Xie, Qing
Pang, Chaoyi
Zhou, Xiaofang
Zhang, Xiangliang
Deng, Ke
Title Maximum error-bounded Piecewise Linear Representation for online stream approximation
Journal name The VLDB Journal   Check publisher's open access policy
ISSN 1066-8888
Publication date 2014-04-04
Year available 2014
Sub-type Article (original research)
DOI 10.1007/s00778-014-0355-0
Open Access Status
Volume 23
Issue 6
Start page 915
End page 937
Total pages 23
Place of publication New York, NY, United States
Publisher Association for Computing Machinery
Collection year 2015
Language eng
Abstract 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 (Formula presented.) 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.
Keyword Stream approximation
Error bound
Piecewise Linear Representation
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2015 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 21 Oct 2014, 02:06:00 EST by System User on behalf of School of Information Technol and Elec Engineering