Исследователи создали метод обработки огромных графов на одном компьютере
Новая технология T-GPS, позволяющая обрабатывать огромные графы без сохранения в оперативной или постоянной памяти, разработана исследовательской группой из Корейского института передовых технологий (KAIST) под руководством профессора Мин-Су Кима, 6 мая сообщает британский журнал об электронике Electronics Weekly.
«Графы широко используются для представления и анализа объектов реального мира во многих областях, таких как социальные сети, бизнес-аналитика, биология и нейробиология», — заявил Ким.
Количество приложений, использующих представление данных в виде графов быстро растет. Параллельно растут объемы данных, которые необходимо обрабатывать и представлять. Поэтому потребность в новых алгоритмах высокая, считают исследователи.
Типовые алгоритмы представления данных в виде графов работают в два этапа. Сначала формируется граф и сохраняется в оперативную память или на постоянный накопитель. Затем на подготовленных данных выполняется алгоритм укладки, либо иной обработки.
Группа из KAIST разработала алгоритм T-GPS (моделирование обработки графов в триллионном масштабе). T-GPS работает за один проход. Он формирует небольшой граф на реальных данных, а затем синтезирует и обрабатывает только ту часть графа, которая сейчас непосредственно необходима.
Используя такой подход, группа смогла обработать граф с 1 трлн ребер на одном компьютере. При этом накладные расходы на размещение в памяти и обработку оказались ниже в 10 тыс. раз, а скорость выше в 43 раза. Последнее обусловлено, в частности, отсутствием необходимости в сетевом обмене между вычислительными узлами кластера.
