An optimal online semi-connected PLA algorithm with maximum error bound

Huanyu Zhao; Chaoyi Pang; Ramamohanarao Kotagiri; Christopher K. Pang; Ke Deng; Jian Yang; Tongliang Li

doi:10.1109/TKDE.2020.2981319

An optimal online semi-connected PLA algorithm with maximum error bound

Huanyu Zhao, Chaoyi Pang^*, Ramamohanarao Kotagiri, Christopher K. Pang, Ke Deng, Jian Yang, Tongliang Li^*

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of 'semi-connection' that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions.

Original language	English
Pages (from-to)	164-177
Number of pages	14
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	34
Issue number	1
DOIs	https://doi.org/10.1109/TKDE.2020.2981319
Publication status	Published - Jan 2022

Keywords

Bounded error in approximation
Data stream
Online algorithm
Piecewise linear approximation (PLA)
Semi-connected
Time series

Access to Document

10.1109/TKDE.2020.2981319

Cite this

@article{b4f26db290ae4c7d98055f6c1e7834d7,

title = "An optimal online semi-connected PLA algorithm with maximum error bound",

abstract = "Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of 'semi-connection' that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions. ",

keywords = "Bounded error in approximation, Data stream, Online algorithm, Piecewise linear approximation (PLA), Semi-connected, Time series",

author = "Huanyu Zhao and Chaoyi Pang and Ramamohanarao Kotagiri and Pang, {Christopher K.} and Ke Deng and Jian Yang and Tongliang Li",

year = "2022",

month = jan,

doi = "10.1109/TKDE.2020.2981319",

language = "English",

volume = "34",

pages = "164--177",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

number = "1",

}

TY - JOUR

T1 - An optimal online semi-connected PLA algorithm with maximum error bound

AU - Zhao, Huanyu

AU - Pang, Chaoyi

AU - Kotagiri, Ramamohanarao

AU - Pang, Christopher K.

AU - Deng, Ke

AU - Yang, Jian

AU - Li, Tongliang

PY - 2022/1

Y1 - 2022/1

N2 - Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of 'semi-connection' that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions.

AB - Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of 'semi-connection' that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions.

KW - Bounded error in approximation

KW - Data stream

KW - Online algorithm

KW - Piecewise linear approximation (PLA)

KW - Semi-connected

KW - Time series

UR - http://www.scopus.com/inward/record.url?scp=85121744714&partnerID=8YFLogxK

U2 - 10.1109/TKDE.2020.2981319

DO - 10.1109/TKDE.2020.2981319

M3 - Article

AN - SCOPUS:85121744714

SN - 1041-4347

VL - 34

SP - 164

EP - 177

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 1

ER -

An optimal online semi-connected PLA algorithm with maximum error bound

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this