Sunday, November 2, 2014

HighLoad++ 2014: Thorny path to the Large-Scale Graph Processing (Алексей Зиновьев, Тамтэк)

(Доклады с HighLoad++ 2014)

В продолжение предыдущего поста, материалы с еще одного доклада с очередной конференции разработчиков высоконагруженных систем HighLoad++ 2014. В данном случае это слайды с доклада Алексея Зиновьева из Тамтэк: Thorny path to the Large-Scale Graph Processing.

Из описания доклада с сайта HighLoad++ 2014:

Алексей Зиновьев (Тамтэк) - один из организаторов Google Developer Group Omsk, Java-разработчик в компании "Тамтэк", аспирант ОмГУ, специализирующийся в исследовании транспортных сетей, дорожных графов, хранении и обработке больших данных. Биография: увлеченный разработчик мобильных приложений и хранилищ данных. В большинстве рабочих проектов используются такие технологии, как Cassandra, MongoDB, Riak, Neo4j, Android, iOS, Google Maps API, Yandex Maps API, а также технологии семейства Open Street Map. В исследовательских проектах часто используется Hadoop для обработки больших массивов геоданных и больших дорожных графов, а также различные алгоритмы из областей Data Mining, Machine Learning для предсказания дорожных заторов и выявления неустойчивых элементов сети. Один из лидеров Google Developer Group Omsk. В 2013 году Алексей организовал и провел в Омске две конференции: "Hello, Android!" и GDG DevFest.

Сети вокруг нас. Любой объект окружающего нас мира можно представить в виде совокупности объектов и связей между ними. Если объектов становится слишком много, а связи между ними слишком сложны, поневоле приходится задуматься о том, как эффективно хранить и обрабатывать такую сеть. Классические алгоритмы и структуры данных "пасуют" уже на сравнительно небольших графах.

Что делать, если объект вашего исследования - это весь веб-граф Рунета, граф Твиттера, дорожная сеть Европейского союза или граф знаний Google? Как корректно и быстро вычислить диаметр графа, найти компоненты связности, кратчайшее расстояние между всеми парами вершин или разрушить минимальное остовное дерево?

Многие без оглядки "бросаются в омут" Neo4j и других графовых баз данных, кто-то изобретает свои способы компактного хранения графа в оперативной памяти, а некоторые прибегают к мощи парадигмы MapReduce.

Традиционная MapReduce-парадигма не оправдывает себя при выполнении расчетов на больших графах. Большинство современных фреймворков обработки графов построены по модели "Bulk Synchronous Parallel", в том числе и знаменитые Pregel и Apache Giraph.

Дивный мир Graph Mining и Large-Scale Graph Processing приковывает к себе взгляды многих исследовательских компаний и увлеченных теорией графов программистов, вовлекая их в процесс создания новых алгоритмов и открытых инструментов. Это увлекательный, но тернистый путь, но дорогу, как известно, осилит идущий.

No comments:

Post a Comment