Memory-efficient sensor data compression

Memory-efficient sensor data compression

Автор: Shevchuk Yury Vladimirovich

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем

Статья в выпуске: 2 (53) т.13, 2022 года.

Бесплатный доступ

We treat scalar data compression in sensor network nodes in streaming mode (compressing data points as they arrive, no pre-compression buffering). Several experimental algorithms based on linear predictive coding (LPC) combined with run length encoding (RLE) are considered. In entropy coding stage we evaluated (a) variable-length coding with dynamic prefixes generated with MTF-transform, (b) adaptive width binary coding, and (c) adaptive Golomb-Rice coding. We provide a comparison of known and experimental compression algorithms on 75 sensor data sources. Compression ratios achieved in the tests are about 1.5/4/1000000 (min/med/max), with compression context size about 10 bytes.

Еще

Lpc, linear predictive coding, dtn, delay tolerant network, laplace distribution, adaptive compression, bookstack, mtf transform, rle, rlgr, prefix code, elias gamma coding, golomb-rice coding, vbinary coding

Короткий адрес: https://sciup.org/143178813

IDR: 143178813   |   DOI: 10.25209/2079-3316-2022-13-2-35-63

Список литературы Memory-efficient sensor data compression

  • K. Fall. "A delay tolerant network architecture for challenged internets", SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications (August 25-29, 2003, Karlsruhe, Germany), ACM, New York, 2003, ISBN 978-1-58113-735-4, pp. 27-34.
  • C. M. Sadler, M. Martonosi. "Data compression algorithms for energy-constrained devices in delay tolerant networks", SenSys '06: Proceedings of the 4th international conference on Embedded networked sensor systems (31 October 2006-3 November 2006, Boulder, Colorado, USA), ACM, New York, 2006, ISBN 978-1-59593-343-0, pp. 265-278.
  • S. Arrabi, J. Lach. "Adaptive lossless compression in wireless body sensor networks", BodyNets '09: Proceedings of the Fourth International Conference on Body Area Networks (April 1-3, 2009, Los Angeles, CA, USA), ICST, Brussels, 2010, ISBN 978-963-9799-41-7.
  • J. G. Kolo, S. A. Shanmugam, D. W. G. Lim, L. M. Ang. "Fast and efficient lossless adaptive compression scheme for wireless sensor networks", Computers & Electrical Engineering, 41 (2015), pp. 275-287
  • F. Huang, Y. Liang. "Towards energy optimization in environmental wireless sensor networks for lossless and reliable data gathering", IEEE International Conference on Mobile Adhoc and Sensor Systems (08-11 October 2007, Pisa, Italy), 2007, pp. 1-6.
  • J. Coalson, Description of the FLAG format
  • T. Robinson. SHORTEN: Simple lossless and near-lossless waveform compression, Technical report CUED/F-INFENG/TR.156, 1994, 16 pp.
  • T. Pelkonen, P. Cavallaro, Q. Huang, S. Franklin, J. Meza, J. Teller, K. Veerara.ghfl.van. "Gorilla.: a. fast, scalable, in-memory time series database", Proceedings of the VLDB Endowment, 8:12 (2015), pp. 1816-1827.
  • E. Lazin. Compression algorithms in Akumuli.
  • F. Jazizadeh, M. Afzalan, B. Becerik-Gerber, L. Soibelman. "EMBED: A dataset for energy monitoring through building electricity disaggregation", e-Energy '18: Proceedings of the Ninth International Conference on Future Energy Systems (June 12-15, 2018, Karlsruhe, Germany), ACM, New York, 2018, ISBN 978-1-4503-5767-8, pp. 230-235.
  • Digital Humidity Sensor SHTW2 (RH/T), Datasheet, Sensirion AG, Switzerland, 14 pp.
  • D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Data compression techniques. Archiver internals, compressing images and video, DIALOG-MIFI, M., 2002, isbn 5-86404-170-X (in Russian), 384 pp.
  • P. Ratanaworabhan, J. Ke, M. Burtscher. "Fast lossless compression of scientific floating-point data", Data Compression Conference, DCC'06 (28-30 March 2006, Snowbird, UT, USA), IEEE Computer Society, 2006, ISBN 0-7695-2545-8, pp. 133-142.
  • M. Burtscher, P. Ratanaworabhan. "High throughput compression of double-precision floating-point data", Data Compression Conference, DCC'07 (27-29 March, 2007, Snowbird, UT, USA), IEEE Computer Society, 2007, ISBN 0-7695-2791-4, pp. 293-302.
  • M. Hans, R. W. Schafer. Lossless compression of digital audio, HPL-1999-144, Hewlett-Packard Company, 1999, 37 pp.
  • Yu. A. Reznik. "Coding of prediction residual in MPEG-4 standard for lossless audio coding (MPEG-4 ALS)", 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing (17-21 May 2004, Montreal, QC, Canada), 2004, ISBN 0-7803-8484-9.
  • C. C. Cutler. Differential quantization of communication signals, U.S. patent 2605361, 1950.
  • D. Salomon. Data Compression. The Complete Reference, 4th ed., SpringerVerlag, London, 2007, ISBN 978-1-84628-602-5, xxviii+1092 pp.
  • S.W. Golomb. "Run-length encodings", IEEE Transactions on Information Theory, 12:3 (1966), pp. 399-401.
  • R. F. Rice, J. R. Plaunt. "Adaptive variable-length coding for efficient compression of spacecraft television data", IEEE Transactions on Communication Technology, 19:6 (1971), pp. 889-897.
  • N. Faller. "An Adaptive System for Data Compression", 7th Asilomar Conference on Circuits, Systems, and Computers, 1973, pp. 593-597.
  • D. Marpe, H. Schwarz, T. Wiegand. "Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard", IEEE Transactions on Circuits and Systems for Video Technology, 13:7 (2003), pp. 620-636.
  • B.Ya. Ryabko. "Szhatiye dannykh s pomoshch'yu stopki knig", Prob-lemy peredachi informormatsii, XVI:4 (1980), pp. 16-20 (in Russian); B.Ya. Ryabko. "Data compression by means of a "book stack"", Problems of Information Transmission, 16:4 (1980), pp. 265-269.
  • H. M. Malvar. "Adaptive run-length/Golomb-Rice encoding of quantized generalized Gaussian sources with unknown statistics", Data Compression Conference, DCC'06 (28-30 March 2006, Snowbird, UT, USA), IEEE Computer Society, 2006, ISBN 0-7695-2545-8, pp. 23-32.
  • J. Durbin. "The fitting of time-series models", JSTOR: Revue de l'Institut International de Statistique, 28:3 (1960), pp. 233-344.
  • I. Schiopu, A. Munteanu. "Deep-learning-based lossless image coding", IEEE Transactions on Circuits and Systems for Video Technology, 30:7 (2020), pp. 1829-1842.
  • M. Goyal, K. Tatwawadi, S. Chandak, I. Ochoa. "DZip: improved generalpurpose loss less compression based on novel neural network modeling", 2021 Data Compression Conference, DCC (23-26 March 2021, Snowbird, UT, USA), IEEE, 2021, pp. 153-162.
  • Y. Collet, Kucherawy M. (eds.). Zstandard compression and the 'applica-tion/zstd' media type, RFC 8878, 2018, 54 pp.
  • J. Ziv, A. Lempel. "A universal algorithm for sequential data compression", IEEE Transactions on Information Theory, 23:3 (1977), pp. 337-343.
  • J. Duda. Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, 2014, 24 pp.
  • R. F. Rice, P. S. Yeh, W. Miller. Algorithms for a very high speed universal noiseless coding module, JPL Publication 91-1, Jet Propulsion Laboratory, Pasadena, 1991, 30 pp. url;
  • P. Elias. "Universal codeword sets and representations of the integers", IEEE Transactions on Information Theory, 21:2 (1975), pp. 194-203.
  • J.L. Bentley, D.D. Sleator, R. E. Tarjan, V. K. Wei. "A locally adaptive data compression scheme", Communications of the ACM, 29:4 (1986), pp. 320-330.
  • Yu. Shevchuk. "Vbinary: variable length integer coding revisited", Program, Systems: Theory and Applications, 9:4(39) (2018), pp. 239-252.
  • H. G. Dietz. The Aggregate Magic Algorithms, Aggregate.Org online technical report, LTniversity of Kentucky, 2021.
  • A. Kiely. Selecting the Golomb parameter in Rice coding, IPN Progress Report 42-159, 2004, 18 pp.
Еще
Статья научная
SciUp 2024 © 2024 ©