RD-GST: онлайн метод побудови розподілених узагальнених суфіксних дерев

Садовий, Я.С.; Воротнiков, В.В.; Sadovyi, I.S.; Vorotnikov, V.V.

RD-GST: онлайн метод побудови розподілених узагальнених суфіксних дерев

Садовий, Я.С.; Воротнiков, В.В.; Sadovyi, I.S.; Vorotnikov, V.V.

URI: https://eztuir.ztu.edu.ua/123456789/9171

Дата: 2026

Анотація:

Узагальнені суфіксні дерева (УСД) є фундаментальними структурами даних для точного пошуку підрядків із лінійною часовою складністю O(m) відносно довжини запиту m, незалежно від розміру індексованого корпусу. Завдяки цій властивості УСД широко застосовуються в аналізі геномних послідовностей та індексуванні великих текстових масивів. Попри це, переважна більшість розподілених реалізацій УСД є офлайн-орієнтованими: вони будують індекс для статичного набору рядків, а надходження нових даних вимагає повної або істотної реконструкції структури. Це унеможливлює їх застосування в аналітичних платформах із безперервними потоками даних, що потребують одночасно високої швидкості та точності пошуку. Метою роботи є розроблення методу побудови розподіленого узагальненого суфіксного дерева, придатного для інкрементальної обробки потокових даних у кластерному середовищі без повної перебудови індексу при надходженні нових рядків. Запропоновано метод RD-GST, який поєднує інкрементальну стратегію конструювання суфіксного дерева з хеш-орієнтованою схемою розподілу рядків між вузлами обчислювального кластера. Метод реалізовано в архітектурі «координатор – робочі вузли» у контейнеризованому середовищі на базі Docker та AWS ECS. Принцип локальності оброблення мінімізує обсяг міжвузлових комунікацій і забезпечує інкрементальне оновлення індексу без повної реконструкції. Для оцінювання ефективності проведено порівняльний експеримент із методом DGST на підвибірках корпусу DNS-імен обсягом 100–600 млн символів за однакових обчислювальних ресурсів. RD-GST забезпечує прискорення у 3,2–5,1 разу та пропускну здатність 5,1–5,5 млн символів/с проти 0,9–1,7 млн символів/с для DGST. Перевага у швидкодії супроводжується інтенсивнішим споживанням оперативної пам’яті, що потребує пропорційного нарощування ресурсів зі збільшенням обсягу корпусу. Доведено практичну ефективність онлайн-підходу для потокової обробки текстових корпусів у реальному часі. Усі результати відтворювані на основі відкритих програмних реалізацій за узгоджених експериментальних умов.

Анотація (англ.):

Generalized suffix trees (GST) are fundamental data structures for exact substring search with linear time complexity O(m) with respect to query length m, regardless of the size of the indexed corpus. This property makes GSTs widely applicable in genomic sequence analysis and large-scale text corpus indexing. However, the majority of existing distributed GST implementations are offline-oriented: they construct the index for a static string collection, and the arrival of new data requires full or substantial reconstruction of the structure. This makes them unsuitable for analytical platforms operating on continuous data streams that demand both high throughput and exact search accuracy. The objective of this work is to develop a method for constructing a distributed generalized suffix tree capable of incremental processing of streaming data in a cluster environment without full index reconstruction upon the arrival of new strings. The proposed RD-GST method combines an incremental suffix tree construction strategy with a hash-oriented string distribution scheme across cluster nodes. The method is implemented following a coordinator–worker architecture in a containerized environment based on Docker and AWS ECS. A data locality principle minimizes inter-node communication overhead and ensures incremental index updates without full reconstruction. To evaluate performance, a comparative experiment with the DGST method was conducted on subsets of a DNS name corpus ranging from 100 to 600 million characters under identical computational resources. RD-GST achieves a speedup of 3.2–5.1× and a throughput of 5.1–5.5 million characters/s compared to 0.9–1.7 million characters/s for DGST. The performance advantage is accompanied by higher memory consumption, requiring proportional resource scaling as corpus size increases. The practical efficiency of the online approach for real-time streaming text corpus processing has been demonstrated. All results are reproducible using open-source implementations under controlled experimental conditions.

Показати повний опис матеріалу