Sim-Piece: Highly Accurate Piecewise Linear Approximation through Similar Segment Merging
Proceedings of the VLDB Endowment · 2023-04 · 16 (8) · 1910-1922
DOI: 10.14778/3594512.3594521 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 22.06.2023. Verfasst von Xenophon Kitsios und 3 weiteren Autor:innen. Die Arbeit wurde bisher 32-mal zitiert (Crossref) und nennt 34 Literaturangaben.
Abstract (Originalsprache)
Approximating series of timestamped data points using a sequence of line segments with a maximum error guarantee is a fundamental data compression problem, termed as piecewise linear approximation (PLA). Due to the increasing need to analyze massive collections of time-series data in diverse domains, the problem has recently received significant attention, and recent PLA algorithms that have emerged do help us handle the overwhelming amount of information, at the cost of some precision loss. More specifically, these algorithms entail a trade-off between the maximum precision loss and the space savings achieved. However, advances in the area of lossless compression are undercutting the offerings of PLA techniques in real datasets. In this work, we propose Sim-Piece, a novel lossy compression algorithm for time-series data that optimizes the space requirements of representing PLA line segments, by finding the minimum number of groups we can organize these segments into, to represent them jointly. Our experimental evaluation demonstrates that our approach readily outperforms competing techniques, attaining compression ratios with more than twofold improvement on average over what PLA algorithms can offer. This allows for providing significantly higher accuracy with equivalent space requirements. Moreover, our algorithm, due to the simplicity of its merging phase, imposes little overhead while compacting the PLA description, offering a significantly improved trade-off between space and running time. The aforementioned benefits of our approach significantly improve the efficiency in which we can store time-series data, while allowing a tight maximum error in the representation of their values.
Zitieren
APA
Kitsios, X., Liakos, P., Papakonstantinopoulou, K., & Kotidis, Y. (2023). Sim-Piece: Highly Accurate Piecewise Linear Approximation through Similar Segment Merging. Proceedings of the VLDB Endowment, 16(8), 1910-1922. https://doi.org/10.14778/3594512.3594521
Vancouver
Kitsios X, Liakos P, Papakonstantinopoulou K, Kotidis Y. Sim-Piece: Highly Accurate Piecewise Linear Approximation through Similar Segment Merging. Proceedings of the VLDB Endowment. 2023;16(8):1910-1922. doi:10.14778/3594512.3594521
BibTeX
@article{Kitsios2023,
author = {Kitsios, Xenophon and Liakos, Panagiotis and Papakonstantinopoulou, Katia and Kotidis, Yannis},
title = {Sim-Piece: Highly Accurate Piecewise Linear Approximation through Similar Segment Merging},
journal = {Proceedings of the VLDB Endowment},
year = {2023},
volume = {16},
number = {8},
pages = {1910--1922},
doi = {10.14778/3594512.3594521}
}
EUVIMED