Русский
!

Conference publications

Abstracts

XXI conference

Техника репликации для сбалансированной кластеризации модели распределённого графа

Станкевич Е.В.

Россия, 150000, г. Ярославль, ул. Советская, д.14

1 pp. (accepted)

Рост объёма хранимых и обрабатываемых данных в конечном итоге приводит к необходимости увеличения вычислительной мощности систем оперирующих этими данными. Наиболее предпочтительным способом повышения производительности является горизонтальное маштабирование, при котором прирост производительности системы осуществляется за счёт увеличения числа вычислительных узлов. Для систем управления базами данных требуется разработка специальных подходов, позволяющих производить горизонтальное маштабирование в рамках используемой в системе модели данных. В данной работе расматривается поход к горизонтальному маштабированию графовой базы данных, моделью данных которой является граф.Задача горизонтального маштабирования графовой БД пердставляет собой поиск распределённого графа, вершины которого разбиты на заданное число кластеров. Каждый такой кластер представлен на отдельном вычислительном узле. Для обеспечения равномерной нагрузки на вычислительные узлы размеры полученных кластеров должны быть сбалансированы, кроме того величины разрезов графа на кластеры должны быть минимальны для снижения объёма трафика данных, передаваемых между узлами. Задача сбалансированной кластеризации графа является NP-полной, для её решения предлагаются различный эвристики. Одной из таких подходов - алгоритм Ja-be-Ja. Алгоритм является процедурой локального поиска оптимальной раскраски графа в N цветов. Вводится понятие энергии вершины - число смежных вершин отличного от её цвета. Итеративно путём обмена цветов вершин алгоритм производит уменьшение общей энергии, для предотвращения сходимости к локальному минимуму моделируется отжиг. В проведённых авторами экспериментах алгоритм демонстрирует высокое качество кластеризации.

Согласно нашим исследованиям основным недостатком данного алгоритма является зависимость качества кластеризации от заданного числа кластеров. К примеру, при разбиении графа на 2 кластера, при условии фактического наличия в графе 3-х кластеров одинакового размера, из-за жёсткого выполнения требования сбалансированности алгоритм оказывается неспособным найти близкое к оптимальному разбиение. Целью данной работы стала разработка модификации алгоритма Ja-be-Ja, устраняющей недостатки его оригинальной версии. Основная идея предлагаемого подхода заключается в использовании техники репликации вершин графа на нескольких вычислительных узлах таким образом, что локальные реплики представляют собой кеш наиболее используемых вершин соседних кластеров. Для изучения характеристик предложенного метода была разработана и реализована имитационная модель распределённого статичного графа. Анализ полученных данных показал, что предложенный подход может быть применён для проведения более качественной кластеризации графа по сравнению с оригинальной версией алгоритма.



© 2004 Designed by Lyceum of Informational Technologies №1533