RD-GST: онлайн метод побудови розподілених узагальнених суфіксних дерев
DOI:
https://doi.org/10.26642/ten-2026-1(97)-264-270Ключові слова:
узагальнене суфiксне дерево, розподiленi обчислення, потоковi данi, структури даних, текстовий пошукАнотація
Узагальнені суфіксні дерева (УСД) є фундаментальними структурами даних для точного пошуку підрядків із лінійною часовою складністю відносно довжини запиту , незалежно від розміру індексованого корпусу. Завдяки цій властивості УСД широко застосовуються в аналізі геномних послідовностей та індексуванні великих текстових масивів. Попри це, переважна більшість розподілених реалізацій УСД є офлайн-орієнтованими: вони будують індекс для статичного набору рядків, а надходження нових даних вимагає повної або істотної реконструкції структури. Це унеможливлює їх застосування в аналітичних платформах із безперервними потоками даних, що потребують одночасно високої швидкості та точності пошуку. Метою роботи є розроблення методу побудови розподіленого узагальненого суфіксного дерева, придатного для інкрементальної обробки потокових даних у кластерному середовищі без повної перебудови індексу при надходженні нових рядків. Запропоновано метод RD-GST, який поєднує інкрементальну стратегію конструювання суфіксного дерева з хеш-орієнтованою схемою розподілу рядків між вузлами обчислювального кластера. Метод реалізовано в архітектурі «координатор – робочі вузли» у контейнеризованому середовищі на базі Docker та AWS ECS. Принцип локальності оброблення мінімізує обсяг міжвузлових комунікацій і забезпечує інкрементальне оновлення індексу без повної реконструкції. Для оцінювання ефективності проведено порівняльний експеримент із методом DGST на підвибірках корпусу DNS-імен обсягом 100–600 млн символів за однакових обчислювальних ресурсів. RD-GST забезпечує прискорення у 3,2–5,1 разу та пропускну здатність 5,1–5,5 млн символів/с проти 0,9–1,7 млн символів/с для DGST. Перевага у швидкодії супроводжується інтенсивнішим споживанням оперативної пам’яті, що потребує пропорційного нарощування ресурсів зі збільшенням обсягу корпусу. Доведено практичну ефективність онлайн-підходу для потокової обробки текстових корпусів у реальному часі. Усі результати відтворювані на основі відкритих програмних реалізацій за узгоджених експериментальних умов.
Посилання
Ukkonen, E. (1995), «On-line construction of suffix trees», Algorithmica, Vol. 14, No. 3, pp. 249–260, doi: 10.1007/BF01206331.
McCreight, E.M. (1976), «A space-economical suffix tree construction algorithm», Journal of the ACM, Vol. 23, No. 2, pp. 262–272, doi: 10.1145/321941.321946.
Mansour, E. et al. (2011), «ERA: efficient serial and parallel suffix tree construction for very long strings», Proceedings of the VLDB Endowment, Vol. 5, No. 1, pp. 49–60, doi: 10.14778/2047485.2047490.
Zhu, G. et al. (2019), «DGST: efficient and scalable suffix tree construction on distributed data-parallel platforms», Parallel Computing, Vol. 87, pp. 87–102, doi: 10.1016/j.parco.2019.06.002.
Sadovyi, I. and Vorotnikov, V. (2025), «The study of optimization of the segmentation process for building distributed generalized suffix trees», Journal of Theoretical and Applied Information Technology, Vol. 103, No. 9, [Online], available at: https://jatit.org/volumes/Vol103No9/5Vol103No9.pdf
Haag, M. et al. (2025), «Fast and lightweight distributed suffix array construction», in 33rd Annual European Symposium on Algorithms (ESA 2025). Series. Leibniz International Proceedings in Informatics (LIPIcs), Vol. 351, pp. 47:1–47:18, doi: 10.4230/LIPIcs.ESA.2025.47.
Hlybovets, A. and Didenko, V. (2023), «Constructing generalized suffix trees on distributed parallel platforms», Cybernetics and Systems Analysis, Vol. 59, No. 1, pp. 49–60, doi: 10.1007/s10559-023-00541-x.
Takagi, T. et al. (2020), «Fully-online suffix tree and directed acyclic word graph construction for multiple texts», Algorithmica, Vol. 82, doi: 10.1007/s00453-019-00646-w.
Hendrian, D. et al. (2024), «Linear time online algorithms for constructing linear-size suffix trie», Theoretical Computer Science, Vol. 1015, doi: 10.1016/j.tcs.2024.114765.
Marchese, A. and Tomarchio, O. (2025), «Enhancing the Kubernetes platform with a load-aware orchestration strategy», SN Computer Science, Vol. 6, No. 3, 224 p., doi: 10.1007/s42979-025-03712-z.
Domains Project, «Domains Project: processing petabytes of data», [Online], available at: https://domainsproject.org/
PasaLab, «DGST» [Source code], GitHub, [Online], available at: https://github.com/PasaLab/DGST
GitHub: iansadovy/DGST, [Online], available at: https://github.com/iansadovy/DGST
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2026 Ян Станiславович Садовий, Володимир Володимирович Воротнiков
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
Автор, який подає матеріали до друку, зберігає за собою всі авторські права та надає відповідному виданню право першої публікації, дозволяючи розповсюджувати даний матеріал із зазначенням авторства та джерела первинної публікації, а також погоджується на розміщення її електронної версії на сайті Національної бібліотеки ім. В.І. Вернадського.
