В настоящее время технологии распределенных вычислений широко используются для обработки информации в различных областях, от современных промышленных предприятий до анализа социальных сетей. Существуют технологии распределенных вычислений для обработки данных различной природы, в частности, большое распространение получили технологии обработки графовых данных. К ним относится модель Pregel и ее различные аналоги, а также построенные на их основе графовые платформы параллельной обработки больших данных, такие, как Apache Spark GraphX, Apache Giraph, Graphlab и т.д.

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

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

В докладе рассматривается подход к решению проблемы обработки метаграфов в распределенных вычислительных инфраструктурах. Обсуждается представление метаграфа с помощью модели плоского графа и архитектура системы обработки данных в форме метаграфа с использованием графовой платформы параллельной обработки. Также рассматриваются возможные сферы применения метаграфовой модели с использованием описанной системы. В частности, рассматривается предметная область анализа научных публикаций как пример метаграфа. Приводятся результаты экспериментов по распределенной обработке метаграфов на примере задачи поиска кратчайшего пути в графе.

Слайды доклада

Видео доклада.

Литература:

1. Basu A., Blanning R. Metagraphs and their applications. Springer, 2007. 174 p.
2. Voloshin Vitaly I. Introduction to Graph and Hypergraph Theory. Nova Science Publishers, Inc., 2009, 287 p.
3. Johnson J. Hypernetworks in the Science of Complex Systems. London, Imperial College Press, 2013. 349 p.
4. Черненький В.М., Гапанюк Ю.Е., Ревунков Г.И., Терехов В.И., Каганов Ю.Т. Метаграфовый подход для описания гибридных интеллектуальных информационных систем. Прикладная информатика. 2017. № 3 (69). Том 12. С. 57–79.
5. Самохвалов Э.Н., Ревунков Г.И., Гапанюк Ю.Е. Использование метаграфов для описания семантики и прагматики информационных систем. Вестник МГТУ им. Н.Э. Баумана. Сер. «Приборостроение». 2015. Выпуск №1. С. 83-99.
6. Черненький В.М., Терехов В.И., Гапанюк Ю.Е. Структура гибридной интеллектуальной информационной системы на основе метаграфов. Нейрокомпьютеры: разработка, применение. 2016. Выпуск №9. С. 3-14.
7. Гапанюк Ю.Е., Ревунков Г.И., Федоренко Ю.С. Предикатное описание метаграфовой модели данных. Информационно-измерительные и управляющие системы. 2016. Выпуск № 12. С. 122-131.
8. M. Han, K. Daudjee, K Ammar, M.T. O?zsu, X. Wang, T. Jin. An Experimental Comparison of Pregel-like Graph Processing Systems. In: Proceedings of the VLDB Endowment, 7(12):1047-1058, 2014. [Online]. Available: https://www.vldb.org/pvldb/vol7/p1047-han.pdf
9. R.S. Xin, D. Crankshaw, A. Dave, J.E. Gonzalez, M.J. Franklin, I. Stoica. GraphX: Unifying Data-Parallel and Graph-Parallel Analytics. arXiv preprint arXiv:1402.2394, February 2014. [Online]. Available: https://arxiv.org/pdf/1402.2394.pdf
10. G. Malewicz, M.H. Austern, A.J.C. Bik, J. Dehnert, I. Horn, N. Leiser, G. Czajkowski. Pregel: A System for Large-scale Graph Processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data SIGMOD ’10, ACM, pp. 135–146. doi: 10.1145/1582716.1582723
11. R. Shaposhnik, C. Martella, D. Logothetis. Practical Graph Analytics with Apache Giraph. Apress, 2015.
12. I. Robinson, J. Webber, E. Eifrem. Graph Databases: New Opportunities for Connected Data. O'Reilly Media, 2015.