1. Електронний архів Державного університету «Житомирська політехніка»
  2. Фахові видання
  3. Технічна інженерія
Please use this identifier to cite or link to this item: https://eztuir.ztu.edu.ua/123456789/9171
Full metadata record
DC FieldValueLanguage
dc.contributor.authorСадовий, Я.С.-
dc.contributor.authorВоротнiков, В.В.-
dc.contributor.authorSadovyi, I.S.-
dc.contributor.authorVorotnikov, V.V.-
dc.date.accessioned2026-07-22T08:12:56Z-
dc.date.available2026-07-22T08:12:56Z-
dc.date.issued2026-
dc.identifier.urihttps://eztuir.ztu.edu.ua/123456789/9171-
dc.description.abstractУзагальнені суфіксні дерева (УСД) є фундаментальними структурами даних для точного пошуку підрядків із лінійною часовою складністю 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. Перевага у швидкодії супроводжується інтенсивнішим споживанням оперативної пам’яті, що потребує пропорційного нарощування ресурсів зі збільшенням обсягу корпусу. Доведено практичну ефективність онлайн-підходу для потокової обробки текстових корпусів у реальному часі. Усі результати відтворювані на основі відкритих програмних реалізацій за узгоджених експериментальних умов.uk_UA
dc.language.isoukuk_UA
dc.publisherДержавний університет "Житомирська політехніка"uk_UA
dc.relation.ispartofseriesТехнічна інженерія;1(97)-
dc.subjectузагальнене суфiксне деревоuk_UA
dc.subjectрозподiленi обчисленняuk_UA
dc.subjectпотоковi данiuk_UA
dc.subjectструктури данихuk_UA
dc.subjectтекстовий пошукuk_UA
dc.subjectgeneralized suffix treeuk_UA
dc.subjectdistributed computinguk_UA
dc.subjectstreaming datauk_UA
dc.subjectdata structuresuk_UA
dc.subjecttext searchuk_UA
dc.titleRD-GST: онлайн метод побудови розподілених узагальнених суфіксних деревuk_UA
dc.title.alternativeRD-GST: online method for constructing distributed generalized suffix treesuk_UA
dc.typeArticleuk_UA
dc.description.abstractenGeneralized 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.uk_UA
Appears in Collections:Технічна інженерія

Files in This Item:
File Description SizeFormat 
31. Садовий.pdf641.95 kBAdobe PDFView/Open
Show simple item record


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.