{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T14:09:20Z","timestamp":1779890960185,"version":"3.53.1"},"reference-count":18,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T00:00:00Z","timestamp":1527033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Piecewise linear approximation of sensor signals is a well-known technique in the fields of Data Mining and Activity Recognition. In this context, several algorithms have been developed, some of them with the purpose to be performed on resource constrained microcontroller architectures of wireless sensor nodes. While microcontrollers are usually constrained in computational power and memory resources, all state-of-the-art piecewise linear approximation techniques either need to buffer sensor data or have an execution time depending on the segment\u2019s length. In the paper at hand, we propose a novel piecewise linear approximation algorithm, with a constant computational complexity as well as a constant memory complexity. Our proposed algorithm\u2019s worst-case execution time is one to three orders of magnitude smaller and its average execution time is three to seventy times smaller compared to the state-of-the-art Piecewise Linear Approximation (PLA) algorithms in our experiments. In our evaluations, we show that our algorithm is time and memory efficient without sacrificing the approximation quality compared to other state-of-the-art piecewise linear approximation techniques, while providing a maximum error guarantee per segment, a small parameter space of only one parameter, and a maximum latency of one sample period plus its worst-case execution time.<\/jats:p>","DOI":"10.3390\/s18061672","type":"journal-article","created":{"date-parts":[[2018,5,24]],"date-time":"2018-05-24T02:55:43Z","timestamp":1527130543000},"page":"1672","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Time and Memory Efficient Online Piecewise Linear Approximation of Sensor Signals"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0370-222X","authenticated-orcid":false,"given":"Florian","family":"Gr\u00fctzmacher","sequence":"first","affiliation":[{"name":"Institute of Applied Microelectronics and Computer Engineering, University of Rostock, 18051 Rostock, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9604-5382","authenticated-orcid":false,"given":"Benjamin","family":"Beichler","sequence":"additional","affiliation":[{"name":"Institute of Applied Microelectronics and Computer Engineering, University of Rostock, 18051 Rostock, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6254-4271","authenticated-orcid":false,"given":"Albert","family":"Hein","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Rostock, 18051 Rostock, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Kirste","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Rostock, 18051 Rostock, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1568-5423","authenticated-orcid":false,"given":"Christian","family":"Haubelt","sequence":"additional","affiliation":[{"name":"Institute of Applied Microelectronics and Computer Engineering, University of Rostock, 18051 Rostock, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,5,23]]},"reference":[{"key":"ref_1","unstructured":"Keogh, E., Chu, S., Hart, D., and Pazzani, M. (December, January 29). An online algorithm for segmenting time series. Proceedings of the IEEE International Conference on Data Mining, ICDM 2001, San Jose, CA, USA."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1010","DOI":"10.1109\/TPDS.2007.1046","article-title":"An energy-efficient data collection framework for wireless sensor networks by exploiting spatiotemporal correlation","volume":"18","author":"Liu","year":"2007","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Pham, N.D., Le, T.D., and Choo, H. (2008, January 13\u201317). Enhance exploring temporal correlation for data collection in WSNs. Proceedings of the IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2008, Ho Chi Minh City, Vietnam.","DOI":"10.1109\/RIVF.2008.4586356"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Van Laerhoven, K., Berlin, E., and Schiele, B. (2009, January 13\u201315). Enabling efficient time series analysis for wearable activity data. Proceedings of the International Conference on Machine Learning and Applications, ICMLA\u201909, Miami Beach, FL, USA.","DOI":"10.1109\/ICMLA.2009.112"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Berlin, E., and Van Laerhoven, K. (2010, January 10\u201314). An on-line piecewise linear approximation technique for wireless sensor networks. Proceedings of the 2010 IEEE 35th Conference on Local Computer Networks (LCN), Denver, CO, USA.","DOI":"10.1109\/LCN.2010.5735832"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Berlin, E., and Van Laerhoven, K. (2012, January 5\u20138). Detecting leisure activities with dense motif discovery. Proceedings of the 2012 ACM Conference on Ubiquitous Computing, Pittsburgh, PA, USA.","DOI":"10.1145\/2370216.2370257"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2010","DOI":"10.1016\/j.patcog.2007.11.016","article-title":"Gesture spotting with body-worn inertial sensors to detect user activities","volume":"41","author":"Junker","year":"2008","journal-title":"Pattern Recognit."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gr\u00fctzmacher, F., Wolff, J.P., Hein, A., Lepidis, P., Dorsch, R., Kirste, T., and Haubelt, C. (November, January 29). Towards energy efficient sensor nodes for online activity recognition. Proceedings of the IECON 2017-43rd Annual Conference of the IEEE Industrial Electronics Society, Beijing, China.","DOI":"10.1109\/IECON.2017.8217455"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Van Laerhoven, K., and Aronsen, A.K. (2007, January 22\u201329). Memorizing what you did last week: Towards detailed actigraphy with a wearable sensor. Proceedings of the 27th International Conference on Distributed Computing Systems Workshops, ICDCSW\u201907, Toronto, ON, Canada.","DOI":"10.1109\/ICDCSW.2007.43"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Lemire, D. (2007, January 26\u201328). A better alternative to piecewise linear time series segmentation. Proceedings of the 2007 SIAM International Conference on Data Mining, Minneapolis, MN, USA.","DOI":"10.1137\/1.9781611972771.59"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2232","DOI":"10.1109\/TPAMI.2010.44","article-title":"Online segmentation of time series based on polynomial least-squares approximations","volume":"32","author":"Fuchs","year":"2010","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Luo, G., Yi, K., Cheng, S.W., Li, Z., Fan, W., He, C., and Mu, Y. (2015, January 13\u201317). Piecewise linear approximation of streaming time series data with max-error guarantees. Proceedings of the 2015 IEEE 31st International Conference on Data Engineering (ICDE), Seoul, Korea.","DOI":"10.1109\/ICDE.2015.7113282"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1080\/00401706.1962.10490022","article-title":"Note on a method for calculating corrected sums of squares and products","volume":"4","author":"Welford","year":"1962","journal-title":"Technometrics"},{"key":"ref_14","unstructured":"Keogh, E., Lin, J., and Fu, A. (2004, January 1\u20134). HOT SAX: Finding the most unusual time series subsequence: Algorithms and applications. Proceedings of the ICDM, Brighton, UK."},{"key":"ref_15","unstructured":"Keogh, E., Lin, J., and Fu, A. (2018, May 23). HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence. Available online: http:\/\/www.cs.ucr.edu\/~eamonn\/discords\/."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1145\/1273442.1250746","article-title":"Valgrind: A framework for heavyweight dynamic binary instrumentation","volume":"Volume 42","author":"Nethercote","year":"2007","journal-title":"Proceedings of the ACM Sigplan Notices"},{"key":"ref_17","unstructured":"(2018, May 23). The Free Software Foundation, the GNU Compiler Collection. Available online: http:\/\/gcc.gnu.org."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Weidendorfer, J., Kowarschik, M., and Trinitis, C. (2004, January 6\u20139). A tool suite for simulation based analysis of memory access behavior. Proceedings of the International Conference on Computational Science, Krak\u00f3w, Poland.","DOI":"10.1007\/978-3-540-24688-6_58"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/6\/1672\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:05:32Z","timestamp":1760195132000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/6\/1672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,23]]},"references-count":18,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2018,6]]}},"alternative-id":["s18061672"],"URL":"https:\/\/doi.org\/10.3390\/s18061672","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,23]]}}}