An optimal L∞-PLA algorithm for trajectory data compression
With the application and development of global positioning system, huge amounts of real-time trajectory data are collected, which gives a challenge for data transmission, storage and analysis. To attack this issue, data compression technology based on piecewise linear approximation (PLA), which is s...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Science Press (China Science Publishing & Media Ltd.)
2024-09-01
|
| Series: | Shenzhen Daxue xuebao. Ligong ban |
| Subjects: | |
| Online Access: | https://journal.szu.edu.cn/en/#/digest?ArticleID=2681 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850038418536398848 |
|---|---|
| author | ZHAO Huanyu SUN Guohao LI Tongliang YANG Jian PANG Chaoyi |
| author_facet | ZHAO Huanyu SUN Guohao LI Tongliang YANG Jian PANG Chaoyi |
| author_sort | ZHAO Huanyu |
| collection | DOAJ |
| description | With the application and development of global positioning system, huge amounts of real-time trajectory data are collected, which gives a challenge for data transmission, storage and analysis. To attack this issue, data compression technology based on piecewise linear approximation (PLA), which is simple and intuitive, less compression storage and faster data transmission, has been widely researched. Currently, the optimal online PLA algorithm can not effectively compress multi-dimensional trajectory data. This paper presented a novel multi-dimensional compression problem under maximum error bound (mDisPLA∞), and proposed an optimal online PLA algorithm MDisPLA to solve it. MDisPLA used a divide-and-conquer strategy to extend the one-dimensional optimal PLA algorithm for optimizing compression of multi-dimensional trajectory data. It can generate the minimum number of disconnected straight lines in linear time complexity, and these lines are quality-ensured, i.e., the synchronous error between the original point and corresponding recovered one is controlled. With experimental tests by comparing MDisPLA with the state-of-the-art algorithm implemented based on cone intersection using the synchronous Euclidean distance (CISED) on trajectory data sets, it demonstrates that MDisPLA can be stable to generate the quality-ensured lines. It is faster by 14 times than CISED with lower memory requirements, and can reduce the number of segments by 48% and the storage number by 10.5%. MDisPLA significantly improves processing speed and reduces storage while maintaining compression quality. |
| format | Article |
| id | doaj-art-c64368e879c343329d7774ab3e6bee69 |
| institution | DOAJ |
| issn | 1000-2618 |
| language | English |
| publishDate | 2024-09-01 |
| publisher | Science Press (China Science Publishing & Media Ltd.) |
| record_format | Article |
| series | Shenzhen Daxue xuebao. Ligong ban |
| spelling | doaj-art-c64368e879c343329d7774ab3e6bee692025-08-20T02:56:36ZengScience Press (China Science Publishing & Media Ltd.)Shenzhen Daxue xuebao. Ligong ban1000-26182024-09-0141557458210.3724/SP.J.1249.2024.055741000-2618（2024）05-0574-09An optimal L∞-PLA algorithm for trajectory data compressionZHAO HuanyuSUN GuohaoLI TongliangYANG JianPANG ChaoyiWith the application and development of global positioning system, huge amounts of real-time trajectory data are collected, which gives a challenge for data transmission, storage and analysis. To attack this issue, data compression technology based on piecewise linear approximation (PLA), which is simple and intuitive, less compression storage and faster data transmission, has been widely researched. Currently, the optimal online PLA algorithm can not effectively compress multi-dimensional trajectory data. This paper presented a novel multi-dimensional compression problem under maximum error bound (mDisPLA∞), and proposed an optimal online PLA algorithm MDisPLA to solve it. MDisPLA used a divide-and-conquer strategy to extend the one-dimensional optimal PLA algorithm for optimizing compression of multi-dimensional trajectory data. It can generate the minimum number of disconnected straight lines in linear time complexity, and these lines are quality-ensured, i.e., the synchronous error between the original point and corresponding recovered one is controlled. With experimental tests by comparing MDisPLA with the state-of-the-art algorithm implemented based on cone intersection using the synchronous Euclidean distance (CISED) on trajectory data sets, it demonstrates that MDisPLA can be stable to generate the quality-ensured lines. It is faster by 14 times than CISED with lower memory requirements, and can reduce the number of segments by 48% and the storage number by 10.5%. MDisPLA significantly improves processing speed and reduces storage while maintaining compression quality.https://journal.szu.edu.cn/en/#/digest?ArticleID=2681algorithm theorytime seriestrajectory datacompression algorithmpiecewise linear approximationmaximum error boundsynchronous error bound |
| spellingShingle | ZHAO Huanyu SUN Guohao LI Tongliang YANG Jian PANG Chaoyi An optimal L∞-PLA algorithm for trajectory data compression Shenzhen Daxue xuebao. Ligong ban algorithm theory time series trajectory data compression algorithm piecewise linear approximation maximum error bound synchronous error bound |
| title | An optimal L∞-PLA algorithm for trajectory data compression |
| title_full | An optimal L∞-PLA algorithm for trajectory data compression |
| title_fullStr | An optimal L∞-PLA algorithm for trajectory data compression |
| title_full_unstemmed | An optimal L∞-PLA algorithm for trajectory data compression |
| title_short | An optimal L∞-PLA algorithm for trajectory data compression |
| title_sort | optimal l∞ pla algorithm for trajectory data compression |
| topic | algorithm theory time series trajectory data compression algorithm piecewise linear approximation maximum error bound synchronous error bound |
| url | https://journal.szu.edu.cn/en/#/digest?ArticleID=2681 |
| work_keys_str_mv | AT zhaohuanyu anoptimallplaalgorithmfortrajectorydatacompression AT sunguohao anoptimallplaalgorithmfortrajectorydatacompression AT litongliang anoptimallplaalgorithmfortrajectorydatacompression AT yangjian anoptimallplaalgorithmfortrajectorydatacompression AT pangchaoyi anoptimallplaalgorithmfortrajectorydatacompression AT zhaohuanyu optimallplaalgorithmfortrajectorydatacompression AT sunguohao optimallplaalgorithmfortrajectorydatacompression AT litongliang optimallplaalgorithmfortrajectorydatacompression AT yangjian optimallplaalgorithmfortrajectorydatacompression AT pangchaoyi optimallplaalgorithmfortrajectorydatacompression |