T-GPS позволяет обрабатывать граф с 1 трлн рёбер на одном компьютере

Графы широко используются для представления и анализа объектов реального мира в таких областях, как социальные сети, бизнес-аналитика, биология и нейробиология. Обычно разработка и тестирование алгоритмов графа выполняется в два этапа: 1) создание и сохранение графа и 2) выполнение алгоритма с использованием специализированного движка, такого как Apache GraphX.

Но, как правило, графы слишком велики, чтобы поместиться в основной памяти одного компьютера, поэтому движок обработки графов ​​приходится запускать на кластере из нескольких десятков или сотен компьютеров. Неудивительно, что стоимость двухэтапного подхода заоблачно высока.

Исследовательская группа корейского института KAIST, возглавляемая профессором Мин-Су Кимом (Min-Soo Kim), решила проблему традиционного подхода. Ключевая идея метода, получившего название T-GPS (Trillion-scale Graph Processing Simulation), заключается в создании только той части синтетического графа, к которой алгоритм должен получать доступ на данный момент. Движок обработки графов модифицируется, чтобы распознавать сгенерированную часть в контексте всего синтетического графа.

Авторы нового метода показали, что T-GPS способен обрабатывать граф из 1 триллиона рёбер всего на одном компьютере, тогда как при двухэтапном подходе для этого необходим кластер из одиннадцати таких же компьютеров. Иначе говоря, T-GPS обеспечивает экономию вычислительных ресурсов в 10 000 раз. Кроме того, по скорости обработки алгоритма T-GPS может превосходить традиционный подход в 43 раза благодаря отсутствию необходимости в использовании сетевых коммуникаций между компьютерами.

Профессор Ким считает, что эта работа окажет большое влияние на индустрию ИТ, где графы используются почти повсеместно. «T-GPS может значительно увеличить как масштаб, так и эффективность разработки нового алгоритма графов», — добавил он.