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

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. Перевага у швидкодії супроводжується інтенсивнішим споживанням оперативної пам’яті, що потребує пропорційного нарощування ресурсів зі збільшенням обсягу корпусу. Доведено практичну ефективність онлайн-підходу для потокової обробки текстових корпусів у реальному часі. Усі результати відтворювані на основі відкритих програмних реалізацій за узгоджених експериментальних умов.