0 |
Графы широко используются для представления и анализа объектов реального мира в таких областях, как социальные сети, бизнес-аналитика, биология и нейробиология. Обычно разработка и тестирование алгоритмов графа выполняется в два этапа: 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 может значительно увеличить как масштаб, так и эффективность разработки нового алгоритма графов», — добавил он.
Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365
0 |