Масштабируемое распределённое перечисление подграфов

Перечисление подграфов направлено на поиск всех подграфов большого графа данных, изоморфных заданному графу-шаблону. Поскольку операция изоморфизма подграфов требует значительных вычислительных ресурсов, в последнее время исследователи сосредоточились на решении этой задачи в распределённых средах, таких как MapReduce и Pregel. Среди этих подходов современный алгоритм Twin TwigJoin был доказан как оптимальный для конкретного экземпляра на основе левоглубокой схемы соединения. Однако он по-прежнему плохо масштабируется для больших графов из-за ограничений левоглубокой схемы соединения и требования, чтобы каждая декомпозированная компонента (единица соединения) представляла собой звезду. В данной работе предлагается SEED — масштабируемый подход к перечислению подграфов в распределённой среде. По сравнению с Twin TwigJoin алгоритм SEED возвращает оптимальное решение в обобщённой схеме соединения без ограничений, присущих Twin TwigJoin. В качестве единиц соединения используются как звёзды, так и клики, а для поддержки такого расширения разработан эффективный механизм распределённого хранения графов. Разработана комплексная модель стоимости, оценивающая число соответствий для любого заданного графа-шаблона с учётом степенного распределения степеней вершин в графе данных. Затем левоглубокая схема соединения обобщается и разрабатывается алгоритм динамического программирования для вычисления оптимального кустистого плана соединения. Также учитываются перекрытия между единицами соединения. Наконец, предлагается сжатие клик для дальнейшего повышения эффективности алгоритма за счёт уменьшения числа промежуточных результатов. Проведено всестороннее исследование производительности на нескольких реальных графах, включая граф с миллиардами рёбер. Результаты показывают, что предложенный алгоритм превосходит все другие современные алгоритмы более чем на порядок величины.