{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T12:19:07Z","timestamp":1789215547556,"version":"build-2803163510"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/3594512.3594521","type":"journal-article","created":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T20:28:36Z","timestamp":1687465716000},"page":"1910-1922","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Sim-Piece: Highly Accurate Piecewise Linear Approximation through Similar Segment Merging"],"prefix":"10.14778","volume":"16","author":[{"given":"Xenophon","family":"Kitsios","sequence":"first","affiliation":[{"name":"Athens University of Economics and Business, Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Panagiotis","family":"Liakos","sequence":"additional","affiliation":[{"name":"Athens University of Economics and Business, Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katia","family":"Papakonstantinopoulou","sequence":"additional","affiliation":[{"name":"Athens University of Economics and Business, Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yannis","family":"Kotidis","sequence":"additional","affiliation":[{"name":"Athens University of Economics and Business, Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2015. Zstd. Retrieved May 21 2022 from https:\/\/facebook.github.io\/zstd  2015. Zstd. Retrieved May 21 2022 from https:\/\/facebook.github.io\/zstd"},{"key":"e_1_2_1_2_1","volume-title":"Zhu Yan, Gharghabi Shaghayegh, Ratanamahatana Chotirat Ann, Yanping, Hu Bing, Begum Nurjahan, Bagnall Anthony, Mueen Abdullah, Batista Gustavo, and Hexagon-ML.","author":"Anh Dau Hoang","year":"2018","unstructured":"Dau Hoang Anh , Keogh Eamonn , Kamgar Kaveh , Yeh Chin-Chia Michael , Zhu Yan, Gharghabi Shaghayegh, Ratanamahatana Chotirat Ann, Yanping, Hu Bing, Begum Nurjahan, Bagnall Anthony, Mueen Abdullah, Batista Gustavo, and Hexagon-ML. 2018 . The UCR Time Series Classification Archive . https:\/\/www.cs.ucr.edu\/~eamonn\/time_series_data_2018. Dau Hoang Anh, Keogh Eamonn, Kamgar Kaveh, Yeh Chin-Chia Michael, Zhu Yan, Gharghabi Shaghayegh, Ratanamahatana Chotirat Ann, Yanping, Hu Bing, Begum Nurjahan, Bagnall Anthony, Mueen Abdullah, Batista Gustavo, and Hexagon-ML. 2018. The UCR Time Series Classification Archive. https:\/\/www.cs.ucr.edu\/~eamonn\/time_series_data_2018."},{"key":"e_1_2_1_4_1","first-page":"3","article-title":"STL: A seasonal-trend decomposition","volume":"6","author":"Cleveland Robert B","year":"1990","unstructured":"Robert B Cleveland , William S Cleveland , Jean E McRae , and Irma Terpenning . 1990 . STL: A seasonal-trend decomposition . Journal of Official Statistics 6 , 1 (1990), 3 -- 73 . Robert B Cleveland, William S Cleveland, Jean E McRae, and Irma Terpenning. 1990. STL: A seasonal-trend decomposition. Journal of Official Statistics 6, 1 (1990), 3--73.","journal-title":"Journal of Official Statistics"},{"key":"e_1_2_1_5_1","first-page":"19","article-title":"Data Reduction Techniques in Sensor Networks","volume":"28","author":"Deligiannakis Antonios","year":"2005","unstructured":"Antonios Deligiannakis and Yannis Kotidis . 2005 . Data Reduction Techniques in Sensor Networks . IEEE Data Eng. Bull. 28 , 1 (2005), 19 -- 25 . http:\/\/sites.computer.org\/debull\/A05mar\/kotidis.ps Antonios Deligiannakis and Yannis Kotidis. 2005. Data Reduction Techniques in Sensor Networks. IEEE Data Eng. Bull. 28, 1 (2005), 19--25. http:\/\/sites.computer.org\/debull\/A05mar\/kotidis.ps","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007628"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0173-5"},{"key":"e_1_2_1_8_1","volume-title":"Piecewise Linear Approximation in Data Streaming: Algorithmic Implementations and Experimental Analysis. CoRR abs\/1808.08877","author":"Duvignau Romaric","year":"2018","unstructured":"Romaric Duvignau , Vincenzo Gulisano , Marina Papatriantafilou , and Vladimir Savic . 2018. Piecewise Linear Approximation in Data Streaming: Algorithmic Implementations and Experimental Analysis. CoRR abs\/1808.08877 ( 2018 ). arXiv:1808.08877 Romaric Duvignau, Vincenzo Gulisano, Marina Papatriantafilou, and Vladimir Savic. 2018. Piecewise Linear Approximation in Data Streaming: Algorithmic Implementations and Experimental Analysis. CoRR abs\/1808.08877 (2018). arXiv:1808.08877"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297280.3297552"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687645"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Pierre Geurts. 2001. Pattern Extraction for Time Series Classification. In Principles of Data Mining and Knowledge Discovery. 115--127.  Pierre Geurts. 2001. Pattern Extraction for Time Series Classification. In Principles of Data Mining and Knowledge Discovery. 115--127.","DOI":"10.1007\/3-540-44794-6_10"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807199"},{"key":"e_1_2_1_13_1","volume-title":"Algorithmic graph theory and perfect graphs \/ Martin Charles Golumbic","author":"Charles Martin","unstructured":"Martin Charles . Golumbic. 1980. Algorithmic graph theory and perfect graphs \/ Martin Charles Golumbic . Academic Press New York . xx, 284 p. : pages. Martin Charles. Golumbic. 1980. Algorithmic graph theory and perfect graphs \/ Martin Charles Golumbic. Academic Press New York. xx, 284 p. : pages."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(83)90070-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120410"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/1049-9652(91)90056-P"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijforecast.2003.09.015"},{"key":"e_1_2_1_18_1","first-page":"159","article-title":"An optimal algorithm for approximating a piecewise linear function","volume":"9","author":"Imai Hiroshi","year":"1986","unstructured":"Hiroshi Imai and Masao Iri . 1986 . An optimal algorithm for approximating a piecewise linear function . Journal of information processing 9 , 3 (1986), 159 -- 162 . Hiroshi Imai and Masao Iri. 1986. An optimal algorithm for approximating a piecewise linear function. Journal of information processing 9, 3 (1986), 159--162.","journal-title":"Journal of information processing"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375680"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260811"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551852"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00102"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/882082.882086"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113282"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.48443\/V4AP-NY05"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.48443\/E16C-8686"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872825"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/358746.358758"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1973.5009136"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824078"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1961-0119390-6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565829"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.3.324"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0355-0"},{"key":"e_1_2_1_35_1","volume-title":"Fast Time Sequence Indexing for Arbitrary Lp Norms. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14","author":"Yi Byoung-Kee","year":"2000","unstructured":"Byoung-Kee Yi and Christos Faloutsos . 2000 . Fast Time Sequence Indexing for Arbitrary Lp Norms. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14 , 2000, Cairo, Egypt. Morgan Kaufmann, 385--394. Byoung-Kee Yi and Christos Faloutsos. 2000. Fast Time Sequence Indexing for Arbitrary Lp Norms. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14, 2000, Cairo, Egypt. Morgan Kaufmann, 385--394."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3594512.3594521","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T20:31:58Z","timestamp":1687465918000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3594512.3594521"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4]]},"references-count":34,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10.14778\/3594512.3594521"],"URL":"https:\/\/doi.org\/10.14778\/3594512.3594521","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,4]]},"assertion":[{"value":"2023-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}