Метод сжатия данных журналов событий на основе теории комбинаторной генерации с применением структур деревьев И/ИЛИ

  • Yuriy Vasilyevich Shablya Томский государственный университет систем управления и радиоэлектроники http://orcid.org/0000-0002-9695-7493

Аннотация

Экспоненциальный рост объема производимой современным обществом цифровой информации влечет за собой проблему хранения большого объема данных, в том числе архивных данных. Под архивными данными понимается категория «холодных» данных (это такие данные, которые требуют хранения, но при этом редко используются). Наглядным примером такого рода архивных данных являются данные журналов событий, содержащих краткое описание произошедших в информационной системе событий в хронологическом порядке. Учитывая большой объем архивных данных и редкое их использование, актуальным становится хранение таких данных в сжатом виде. В данной статье рассматривается задача разработки метода сжатия архивных данных на примере данных журналов событий за счет применения алгоритмов комбинаторной генерации. В частности, если зафиксировать некоторое текущее состояние журнала событий, то множество его записей может быть рассмотрено как комбинаторное множество. Тогда, используя алгоритм ранжирования элементов комбинаторного множества, каждая запись журнала событий может быть закодирована одним числом, для хранения которого потребуется меньше памяти. Базируясь на данной идее, предложен метод сжатия данных журналов событий на основе теории комбинаторной генерации с применением структур деревьев И/ИЛИ. Для оценки эффективности предложенного метода рассмотрен пример сжатия данных журналов событий, генерируемых внутри электронных курсов системы Moodle. Результаты экспериментального исследования подтвердили эффективность предложенного метода, а именно: суммарный объем памяти, требуемой для хранения журнала события электронного курса системы Moodle в сжатом виде, имеет меньшее значение по сравнению с существующими методами сжатия текстовых файлов.

Сведения об авторе

Yuriy Vasilyevich Shablya, Томский государственный университет систем управления и радиоэлектроники

старший научный сотрудник лаборатории алгоритмов и технологий исследования дискретных структур, кандидат технических наук

Литература

1. Larin M.V., Surovtseva N.G. Some theoretical issues of archival storage of electronic documents. Herald of an archivist. 2019;(3):809-824. (In Russ., abstract in Eng.) https://doi.org/10.28995/2073-0101-2019-3-809-824
2. Memishi B., Appuswamy R., Paradies M. Cold storage data archives: More than just a bunch of tapes. In: Proceedings of the 15th International Workshop on Data Management on New Hardware (DaMoN'19). New York, NY, USA: Association for Computing Machinery; 2019. Article number: 1. https://doi.org/10.1145/3329785.3329921
3. Pernet C., Svarer C., Blair R., van Horn J.D., Poldrack R.A. On the long-term archiving of research data. Neuroinformatics. 2023;21:243-246. https://doi.org/10.1007/s12021-023-09621-x
4. Liu A., Yu T. Overview of Cloud Storage And Architecture. International Journal of Scientific & Technology Research. Available at: https://ssrn.com/abstract=3649074 (accessed 01.09.2023).
5. Jayasankar U., Thirumal V., Ponnurangam D. A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications. Journal of King Saud University Computer and Information Sciences. 2021;33(2):119-140. https://doi.org/10.1016/j.jksuci.2018.05.006
6. Gupta A., Bansal A., Khanduja V. Modern lossless compression techniques: Review, comparison and analysis. In: 2017 Second International Conference on Electrical, Computer and Communication Technologies (ICECCT). Coimbatore, India: IEEE Computer Society; 2017. p. 1-8. https://doi.org/10.1109/ICECCT.2017.8117850
7. Bakulina M. Efficient lossless compression of large information arrays. Problems of Informatics. 2022;(4):63-69. (In Russ., abstract in Eng.) https://doi.org/10.24412/2073-0667-2022-4-63-69
8. Ko J., Comuzzi M. A Systematic Review of Anomaly Detection for Business Process Event Logs. Business & Information Systems Engineering. 2023;65(7):441-462. https://doi.org/10.1007/s12599-023-00794-y
9. Yao K., Sayagh M., Shang W., Hassan A.E. Improving State-of-the-Art Compression Techniques for Log Management Tools. IEEE Transactions on Software Engineering. 2022;48(8):2748-2760. https://doi.org/10.1109/TSE.2021.3069958
10. Balakrishnan R., Sahoo R. Lossless compression for large scale cluster logs. In: Proceedings 20th IEEE International Parallel & Distributed Processing Symposium. Rhodes, Greece: IEEE Computer Society; 2006. p. 7. https://doi.org/10.1109/IPDPS.2006.1639692
11. Grebennik I.V., Lytvynenko O.S. Generating combinatorial sets with given properties. Cybernetics and Systems Analysis. 2012;48:890-898. https://doi.org/10.1007/s10559-012-9469-9
12. Hartung E., Hoang H.P., Mutze T., Williams A. Combinatorial generation via permutation languages. I. Fundamentals. Transactions of the American Mathematical Society. 2020;375:2255-2291. https://doi.org/10.1090/tran/8199
13. Kruchinin V.V., Titkov .V., Khomich S.L. Approach to development of database based on the generation algorithms and tuple identification. Bulletin of Tomsk Polytechnic University. 2006;309(8):28-31. (In Russ., abstract in Eng.) EDN: HYZVQV
14. Shablya Y., Kruchinin D., Kruchinin V. Method for developing combinatorial generation algorithms based on AND/OR trees and its application. Mathematics. 2020;8(6):962. https://doi.org/10.3390/math8060962
15. Shablya Y.V., Kruchinin D.V. Modification of the algorithm development method for combinatorial generation based on the application of the generating functions theory. Proceedings of TUSUR University. 2019;22(3):55-60. (In Russ., abstract in Eng.) https://doi.org/10.21293/1818-0442-2019-22-3-55-60
16. Kruchinin D.V. Modification of the method for developing combinatorial generation algorithms based on the use of multivariate generating functions and approximations. Proceedings of TUSUR University. 2022;25(1):55-60. (In Russ., abstract in Eng.) https://doi.org/10.21293/1818-0442-2021-25-1-55-60
17. Kruchinin V.V. Presentation of set by means of tree AND/OR. Proceedings of TUSUR University. 2008;(1):107-112. (In Russ., abstract in Eng.) EDN: KUUJLT
18. Kruchinin V. V., Lukschin B. A. Method of coding of information objects on the basis of trees And-Or. Proceedings of TUSUR University. 2010;(1):170-172. (In Russ., abstract in Eng.) EDN: MPWDAR
19. Bojiah J. Effectiveness of Moodle in teaching and learning. Journal of Hunan University Natural Sciences. 2022;49(12):320-328. https://doi.org/10.55463/issn.1674-2974.49.12.33
20. Parise P. A preliminary look at online learner behavior what can the Moodle logs tell us? Bulletin of Kanagawa Prefectural Institute of Language and Culture Studies. 2017;6:15-31. https://doi.org/10.20686/academiakiyou.6.0_15
21. Rotelli D., Monreale A. Processing and understanding Moodle log data and their temporal dimension. Journal of Learning Analytics. 2023;10(2):126-141. https://doi.org/10.18608/jla.2023.7867
22. Athaya H., Nadir R.D.A., Indra Sensuse D., Kautsarina K., Suryono R.R. Moodle Implementation for E-Learning: A Systematic Review. In: Proceedings of the 6th International Conference on Sustainable Information Engineering and Technology (SIET '21). New York, NY, USA: Association for Computing Machinery; 2021. p. 106-112. https://doi.org/10.1145/3479645.3479646
23. Jacob N., Somvanshi P., Tornekar R. Comparative analysis of lossless text compression techniques. International Journal of Computer Applications. 2012;56(3):17-21. https://doi.org/10.5120/8871-2850
24. Tanjung A. S., Nasution S. D. Comparison analysis with Huffman algorithm and Goldbach codes algorithm in file compression text using the method exponential comparison. International Journal of Informatics and Computer Science. 2020;4(1):29-34. http://dx.doi.org/10.30865/ijics.v4i1.1387
25. Kotb A., Hassan S., Hassan H. A Comparative Study Among Various Algorithms for Lossless Airborne LiDAR Data Compression. In: 2018 14th International Computer Engineering Conference (ICENCO). Cairo, Egypt: IEEE Computer Society; 2018. p. 17-21. https://doi.org/10.1109/ICENCO.2018.8636136
Опубликована
2023-10-15
Как цитировать
SHABLYA, Yuriy Vasilyevich. Метод сжатия данных журналов событий на основе теории комбинаторной генерации с применением структур деревьев И/ИЛИ. Современные информационные технологии и ИТ-образование, [S.l.], v. 19, n. 3, p. 564-574, oct. 2023. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/988>. Дата доступа: 26 dec. 2024 doi: https://doi.org/10.25559/SITITO.019.202303.564-574.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук