Progressive Bounded Error Piecewise Linear Approximation with Resolution Reduction for Time Series Data Compression
Today, huge amounts of time series data are sensed continuously by AIoT devices, transmitted to edge nodes, and to data centers. It costs a lot of energy to transmit these data, store them, and process them. Data compression technologies are commonly used to reduce the data size and thus save energy...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-12-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/25/1/145 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841548955897298944 |
|---|---|
| author | Jeng-Wei Lin Shih-wei Liao Yu-Hung Tsai Ching-Che Huang |
| author_facet | Jeng-Wei Lin Shih-wei Liao Yu-Hung Tsai Ching-Che Huang |
| author_sort | Jeng-Wei Lin |
| collection | DOAJ |
| description | Today, huge amounts of time series data are sensed continuously by AIoT devices, transmitted to edge nodes, and to data centers. It costs a lot of energy to transmit these data, store them, and process them. Data compression technologies are commonly used to reduce the data size and thus save energy. When a certain level of data accuracy is sacrificed, lossy compression technologies can achieve better compression ratios. However, different applications may have different requirements for data accuracy. Instead of keeping multiple compressed versions of a time series w.r.t. different error bounds, HIRE hierarchically maintains a tree, where the root records a constant function to approximate the whole time series, and each other node records a constant function to approximate a part of the residual function of its parent for a particular time period. To retrieve data w.r.t. a specific error bound, it traverses the tree from the root down to certain levels according to the requested error bound and aggregates the constant functions on the visited nodes to generate a new bounded error compressed version dynamically. However, the number of nodes to be visited is unknown before the tree traversal completes, and thus the data size of the new version. In this paper, a time series is progressively decomposed into multiple piecewise linear functions. The first function is an approximation of the original time series w.r.t. the largest error bound. The second function is an approximation of the residual function between the original time series and the first function w.r.t. the second largest error bound, and so forth. The sum of the first, second, …, and <i>m</i>-th functions is an approximation of the original time series w.r.t. the <i>m</i>-th error bound. For each iteration, Swing-RR is used to generate a Bounded Error Piecewise Linear Approximation (BEPLA). Resolution Reduction (RR) plays an important role. Eight real-world datasets are used to evaluate the proposed method. For each dataset, approximations w.r.t. three typical error bounds, 5%, 1%, and 0.5%, are requested. Three BEPLAs are generated accordingly, which can be summed up to form three approximations w.r.t. the three error bounds. For all datasets, the total data size of the three BEPLAs is almost the same with the size used to store just one version w.r.t. the smallest error bound and significantly smaller than the size used to keep three independent versions. The experiment result shows that the proposed method, referred to as PBEPLA-RR, can achieve very good compression ratios and provide multiple approximations w.r.t. different error bounds. |
| format | Article |
| id | doaj-art-e2ae965332de4763b8758f77d4bcf8ed |
| institution | Kabale University |
| issn | 1424-8220 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj-art-e2ae965332de4763b8758f77d4bcf8ed2025-01-10T13:21:01ZengMDPI AGSensors1424-82202024-12-0125114510.3390/s25010145Progressive Bounded Error Piecewise Linear Approximation with Resolution Reduction for Time Series Data CompressionJeng-Wei Lin0Shih-wei Liao1Yu-Hung Tsai2Ching-Che Huang3Department of Information Management, Tunghai University, Taichung 407224, TaiwanDepartment of Computer Science and Information Engineering, National Taiwan University, Taipei 10617, TaiwanDepartment of Information Management, Tunghai University, Taichung 407224, TaiwanDepartment of Information Management, Tunghai University, Taichung 407224, TaiwanToday, huge amounts of time series data are sensed continuously by AIoT devices, transmitted to edge nodes, and to data centers. It costs a lot of energy to transmit these data, store them, and process them. Data compression technologies are commonly used to reduce the data size and thus save energy. When a certain level of data accuracy is sacrificed, lossy compression technologies can achieve better compression ratios. However, different applications may have different requirements for data accuracy. Instead of keeping multiple compressed versions of a time series w.r.t. different error bounds, HIRE hierarchically maintains a tree, where the root records a constant function to approximate the whole time series, and each other node records a constant function to approximate a part of the residual function of its parent for a particular time period. To retrieve data w.r.t. a specific error bound, it traverses the tree from the root down to certain levels according to the requested error bound and aggregates the constant functions on the visited nodes to generate a new bounded error compressed version dynamically. However, the number of nodes to be visited is unknown before the tree traversal completes, and thus the data size of the new version. In this paper, a time series is progressively decomposed into multiple piecewise linear functions. The first function is an approximation of the original time series w.r.t. the largest error bound. The second function is an approximation of the residual function between the original time series and the first function w.r.t. the second largest error bound, and so forth. The sum of the first, second, …, and <i>m</i>-th functions is an approximation of the original time series w.r.t. the <i>m</i>-th error bound. For each iteration, Swing-RR is used to generate a Bounded Error Piecewise Linear Approximation (BEPLA). Resolution Reduction (RR) plays an important role. Eight real-world datasets are used to evaluate the proposed method. For each dataset, approximations w.r.t. three typical error bounds, 5%, 1%, and 0.5%, are requested. Three BEPLAs are generated accordingly, which can be summed up to form three approximations w.r.t. the three error bounds. For all datasets, the total data size of the three BEPLAs is almost the same with the size used to store just one version w.r.t. the smallest error bound and significantly smaller than the size used to keep three independent versions. The experiment result shows that the proposed method, referred to as PBEPLA-RR, can achieve very good compression ratios and provide multiple approximations w.r.t. different error bounds.https://www.mdpi.com/1424-8220/25/1/145sensor datatime seriesprogressive data compressionhierarchical residual encodingbounded error piecewise linear approximationSwing-RR |
| spellingShingle | Jeng-Wei Lin Shih-wei Liao Yu-Hung Tsai Ching-Che Huang Progressive Bounded Error Piecewise Linear Approximation with Resolution Reduction for Time Series Data Compression Sensors sensor data time series progressive data compression hierarchical residual encoding bounded error piecewise linear approximation Swing-RR |
| title | Progressive Bounded Error Piecewise Linear Approximation with Resolution Reduction for Time Series Data Compression |
| title_full | Progressive Bounded Error Piecewise Linear Approximation with Resolution Reduction for Time Series Data Compression |
| title_fullStr | Progressive Bounded Error Piecewise Linear Approximation with Resolution Reduction for Time Series Data Compression |
| title_full_unstemmed | Progressive Bounded Error Piecewise Linear Approximation with Resolution Reduction for Time Series Data Compression |
| title_short | Progressive Bounded Error Piecewise Linear Approximation with Resolution Reduction for Time Series Data Compression |
| title_sort | progressive bounded error piecewise linear approximation with resolution reduction for time series data compression |
| topic | sensor data time series progressive data compression hierarchical residual encoding bounded error piecewise linear approximation Swing-RR |
| url | https://www.mdpi.com/1424-8220/25/1/145 |
| work_keys_str_mv | AT jengweilin progressiveboundederrorpiecewiselinearapproximationwithresolutionreductionfortimeseriesdatacompression AT shihweiliao progressiveboundederrorpiecewiselinearapproximationwithresolutionreductionfortimeseriesdatacompression AT yuhungtsai progressiveboundederrorpiecewiselinearapproximationwithresolutionreductionfortimeseriesdatacompression AT chingchehuang progressiveboundederrorpiecewiselinearapproximationwithresolutionreductionfortimeseriesdatacompression |