Сжатие сенсорных данных с малым расходом оперативной памяти

Сжатие сенсорных данных с малым расходом оперативной памяти

Автор: Шевчук Юрий Владимирович

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

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

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

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

Рассматривается задача сжатия скалярных данных в узлах сенсорной сети в потоковом режиме (без накопления блока некомпрессированных данных). Рассмотрено несколько экспериментальных алгоритмов сжатия, основанных на сочетании дельта-кодирования (LPC) с кодированием повторов (RLE). На стадии статистического кодирования применялись: a) код переменной длины с динамическими префиксами, полученными с помощью MTF-преобразования, b) адаптивный бинарный код, c) адаптивные коды Голомба-Райса. Проведено сравнение известных и экспериментальных алгоритмов на 75 источниках сенсорных данных. В тестах достигнуты коэффициенты сжатия порядка 1.5/4/1000000 (мин/медиана/макс) при размере контекста алгоритма сжатия порядка 10 байт.

Еще

Lpc, линейное прогнозирующее кодирование, dtn, сеть устойчивая к разрывам, сеть с эпизодической связностью, распределение лапласа, адаптивный алгоритм сжатия, стопка книг, mtf-преобразование, rle, rlgr, префиксный код, гамма-код элиаса, код голомба-райса, код vbinary

Еще

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

IDR: 143178812   |   DOI: 10.25209/2079-3316-2022-13-2-3-33

Список литературы Сжатие сенсорных данных с малым расходом оперативной памяти

  • Fall K. 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), New York: ACM.- 2003,- ISBN 978-1-58113-735-4.- pp. 27-34. I f
  • Sadler C.M., Martonosi M. Data compression algorithmes 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), New York: ACM.-2006,- ISBN 978-1-59593-343-0,- pp. 265-278. .url. f
  • Arrabi S., Lach J. 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), Brussels: IGST.- 2010.- ISBN 978-963-9799-41-7. f
  • Kolo J. G., Shanmugam S. A., Lim D. W. G., Ang L. M. Fast and efficient lossless adaptive compression scheme for wireless sensor networks // Computers & Electrical Engineering.- 2015,- Vol. 41. pp. 275-287. t
  • Huang F., Liang Y. 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. I t
  • Coalson J., Description of the FLAG format, url;
  • Robinson T. SHORTEN: Simple lossless and near-lossless waveform compression, Technical report CUED/F-INFENG/TR. 156.- 1994,- 16 pp. url;
  • Pelkonen T., Cavallaro P., Huang Q., Franklin S., Meza J., Teller J., Veeraraghavan K. Gorilla: a fast, scalable, in-memory time series database // Proceedings of the VLDB Endowment.- 2015,- Vol. 8,- No. 12,- pp. 1816-1827.
  • Lazin E. Compression algorithms in Akumuli. url
  • Jazizadeh F., Afzalan M., Becerik-Gerber В., Soibelman L. 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), New York: ACM.-2018.- ISBN 978-1-4503-5767-8.-pp. 230-235. 11 f
  • Digital Humidity Sensor SHTW2 (RH/T), Datasheet.- Switzerland: Sensirion AG.- 14 pp. url
  • Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео- М.: ДИАЛОГ-МИФИ,- 2002,- ISBN 5-86404-170-Х.- 384 с. url
  • Ratanaworabhan P., Ke J., Burtscher M. 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. ) @
  • Burtscher M., Ratanaworabhan P. 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. ) @
  • Hans M., Schafer R. W. Lossless compression of digital audio, HPL-1999-144.-Hewlett-Packard Company.- 1999.- 37 pp. url
  • Reznik Yu. A. 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. url;
  • Cutler C. C. Differential quantization of communication signals, U.S. patent 2605361,- 1950. uRL;t
  • Salomon D. Data Compression. The Complete Reference, 4th ed..- London: Springer-Verlag.- 2007.- ISBN 978-1-84628-602-5.- xxviii+1092 pp.
  • Golomb S. W. Run-length encodings // IEEE Transactions on Information Theory.- 1966,- Vol. 12. No. 3,- pp. 399-401. .url
  • Rice R. F., Plaunt J. R. Adaptive variable-length coding for efficient compression of spacecraft television data // IEEE Transactions on Communication Technology.- 1971,- Vol. 19,- No. 6,- pp. 889-897.
  • Faller N. An Adaptive System for Data Compression, 7th Asilomar Conference on Circuits, Systems, and Computers.- 1973.- pp. 593-597.
  • Marpe D., Schwarz H., Wiegand T. Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard // IEEE Transactions on Circuits and Systems for Video Technology.- 2003.- Vol. 13.- No. 7 — pp. 620-636. t
  • Рябко Б. Я. Сжатие данных с помощью стопки книг // Проблемы передачи информормации.- 1980.- Т. XVI.- № 4.- с. 16-20.
  • Malvar H. M. 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. urC
  • Durbin J. The fitting of time-series models // JSTOR: Revue de l'Institut International de Statistique.- I960,- Vol. 28,- No. 3,- pp. 233-344.
  • Schiopu I., Munteanu A. Deep-learning-based lossless image coding // IEEE Transactions on Circuits and Systems for Video Technology.- 2020.- Vol. 30. No. 7,- pp. 1829-1842. d t '
  • Goyal M., Tatwawadi K., Chandak S., Ochoa I. 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. I t
  • Collet Y., Kucherawy M. (eds.) Zstandard compression and the 'applica-tion/zstd' media type, RFC 8878,- 2018,- 54 pp. I t
  • Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory.- 1977,- Vol. 23. No. 3-pp. 337-343. url:
  • Duda J. Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding.- 2014.- 24 pp. arXivt? 1311.2540 \
  • Rice R. F., Yeh P. S., Miller W. Algorithms for a very high speed universal noiseless coding module, JPL Publication 91-1.- Pasadena: Jet Propulsion Laboratory.- 1991.- 30 pp. url
  • Elias P. Universal codeword sets and representations of the integers // IEEE Transactions on Information Theory.- 1975.- Vol. 21.- No. 2.- pp. 194-203. d t
  • Bentley J.L., Sleator D. D., Tarjan R. E., Wei V. K. A locally adaptive data compression scheme // Communications of the ACM.- 1986.- Vol. 29.- No. 4.-pp. 320-330. t
  • Shevchuk Yu. Vbinary: variable length integer coding revisited // Program Systems: Theory and Applications.- 2018,- Vol. 9,- No. 4(39).- pp. 239-252.
  • Dietz H.G. The Aggregate Magic Algorithms, Aggregate.Org online technical report.- University of Kentucky.- 2021. .url
  • Kiely A. Selecting the Golomb parameter in Rice coding, IPN Progress Report 42-159,- 2004,- 18 pp.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp