Метаграфовые агенты
sergey shishkinhttps://bmstu.press/catalog/item/7604/download (стр. 337)
Введение По мере усложнения задач, решаемых при разработке программного обеспечения, возрастают требования к используемым моделям данных. Появление новых областей, таких как искусственный интеллект, вебтехнологии, большие данные и распределенные вычисления, требует разработки соответствующих решаемым задачам способов хранения данных. Использование неэффективных моделей данных может привести к неоправданному росту сложности программного обеспечения, а также негативно отразиться на надежности и производительности разрабатываемых систем. Примером модели данных, отвечающей требования функциональности современного программного обеспечения, является метаграфовая модель, детально рассмотренная в работах [1, 2]. Эта модель является обобщением графовой модели, использующейся в настоящее время во многих СУБД. Метаграф допускает хранение внутри каждой вершины произвольного количества вершин и связей с неограниченной вложенностью. Для обработки метаграфовой модели используются метаграфовые агенты [2]. Реализация метаграфовых агентов может быть различной, в частности, в статье [3] разрабатывается реализация на основе функционального реактивного программирования в оперативной памяти сервера (in-memory решение). При этом количество вершин в реальной метаграфовой модели может измеряться сотнями тысяч и даже миллионами. Поэтому in-memory решение подходит только для обработки относительно небольших метаграфовых моделей, а для обработки реальных моделей требуется иной подход. В настоящее время для обработки больших данных используются специализированные технологии (Big Data фреймворки). В некоторых фреймворках (Apache Spark, Apache Flink) также реализована возможность обработки больших графов. С точки зрения метаграфовой модели у существующих технологий обработки больших графов можно выделить следующие ограничения: В существующих фреймворках реализованы методы обработки для плоских графов (или мультиграфов), в то время как метаграф является моделью сложного графа с эмерджентностью. Таким образом, существующие фреймворки не могут быть напрямую использованы для обработки метаграфовой модели. В существующих фреймворках методы обработки для плоских графов реализованы как внешние процедуры. При этом в рамках метаграфового подхода разработана теория метаграфовых агентов, которая предполагает более сложные варианты обработки метаграфовой модели. В данной статье рассматривается подход к реализации метаграфовых агентов, позволяющих осуществлять полноценную обработку метаграфовых моделей на основе технологий обработки больших данных и больших графов.
Краткое описание метаграфовой модели В данном разделе на основе работ [1, 2] мы кратко рассмотрим метаграфовую модель данных и модель агентов, предназначенных для обработки метаграфовых данных ...
Определение метавершины является рекурсивным. Наличие у метавершин собственных атрибутов и связей с другими вершинами является важной особенностью метаграфов. Это соответствует принципу эмерджентности, т. е. приданию понятию нового качества, несводимости понятия к сумме его составных частей. Фактически, как только вводится новое понятие в виде метавершины, оно «получает право» на собственные свойства, связи и т. д., так как в соответствии с принципом эмерджентности новое понятие обладает новым качеством и не может быть сведено к подграфу базовых понятий. Таким образом, метаграф можно охарактеризовать как «сеть с эмерджентностью», т. е. фрагмент сети, состоящий из вершин и связей, может выступать как отдельное целое.
Метаграфовые агенты ... Антецедентом правила является фрагмент метаграфа, консеквентом правила является множество операций, выполняемых над метаграфом ... определение является рекурсивным. Динамические метаграфовые агенты первого уровня могут обрабатывать статические контейнерные агенты, метаграфовые агенты второго уровня могут обрабатывать метаграфовые агенты первого уровня и так далее. По мере необходимости систему можно надстраивать требуемыми уровнями динамики ...
Представление метаграфа Для построения систем, использующих метаграфовую модель, необходимо определиться со способом физического представления метаграфа для персистентного хранения или обработки в платформах больших данных. Можно рассмотреть различные варианты: реляционное представление, представления метаграфа через множество документов (вложенных или раздельных), представление через обычный граф. Мы провели сравнительный анализ различных вариантов представления. Особенности различных вариантов и эксперименты по сравнению производительности описаны в нашей работе [4]. Эксперименты показали, что представление метаграфа через обычный граф является наиболее предпочтительным. Рассмотрим подробнее метаграфа через граф. Необходимо выделить способ отображения вложенной метаграфовой структуры в плоскую структуру обычного графа. Очевидно, что главной задачей здесь является задание отношения «вложенная вершина» – «родительская вершина» для метавершин и их потомков. Единственным доступным для этого инструментов в графовой модели данных является собственно ребро графа. Поэтому единственным способом отображения метавершины с вложенными вершинами в плоскую структуру графа является использование ребер графа для задания принадлежности вершины к метавершине. Метавершина и каждый из ее потомков становятся отдельными вершинами плоского графа, а между ними возникают ребра. Такая модель естественным образом допускает возможность принадлежности вершины к нескольким родительским метавершинам, так как от любой вершины может исходить произвольное число ребер к родителям. Для представления ребер метаграфа можно было бы использовать собственные ребра плоского графа, однако здесь стоит учитывать, что для ребер метаграфа также задано отношение принадлежности к метавершине. Если две вершины входят в родительскую вершину, то ребро между ними может в нее не входить, или вообще входить в другую вершину. Поэтому ребра метаграфа должны представляться как самостоятельные вершины. Начальная и конечная вершина исходного ребра при этом связывается с вершиной-ребром ребрами плоского графа ...
Архитектура и функционирование системы ... При построении системы по обработке метаграфа в платформе больших данных есть два ключевых вопроса: способ распределения графа по кластеру и способ обработки графа.
Распределение метаграфа Основной параметр графа с точки зрения обработки в платформе больших данных – распределение степеней вершин. Степень вершины – число смежных ей ребер. У графов, имеющих естественное происхождение (графы социальных сетей, дорожные графы и т. п.), часто встречается показательное распределение степеней [5]. Это значит, что в графе есть очень небольшое число вершин, имеющих высокую степень, а большинство вершин имеет низкую степень. Иными словами, только небольшое число вершин смежны с большим числом вершин. При преобразовании метаграфа в граф мы получаем граф, у которого можно ожидать наличия большого числа вершин с высокой степенью. Ими являются собственно метавершины. Представляющие их вершины графа будут смежны вершинам, представляющим содержимое метавершин. Разумеется, топология графа, полученного из метаграфа, будет сильно зависеть от предметной области, но в целом представляется вероятным, что у таких графов будет большее количество вершин с большой степенью по сравнению с графами из реального мира...
Модели обработки Следующим важным вопросом является способ обработки графа, полученного из метаграфа, в платформе по обработке больших данных. Существуют различные подходы обработки графов. Общей чертой подходов, использующихся в современных системах обработки графов, является то, что обработка идет с точки зрения отдельных элементов графа, поскольку граф хранится распределенно. Рассмотрим эти модели применительно к метаграфу.
Модель Pregel Эта модель предполагает последовательность из синхронных итераций. В ходе каждой итерации для каждой вершины графа выполняется пользовательская функция, которая определенным образом модифицирует значение вершины. Далее вершина отправляет сообщения в другие вершины (смежные или нет). Следующая итерация начинается только тогда, когда все вершины будут обработаны....
Модель Signal Collect Также ее называют Scatter-Gather. Эта модель также предполагает итеративную обработку на уровне вершин. Она состоит из двух фаз – signal (отправка сообщений в другие вершины) и collect (прием сообщений и обновление вершины). Возможны два режимы работы. В синхронном режиме эта модель работает аналогично Pregel. В асинхронном режиме нет барьера между итерациями и вершины функционируют как независимые акторы. В этом случае мы не получаем простоя на обработке метавершин. Однако такая модель (в зависимости от решаемой задачи) может требовать локальных блокировок, что усложнит алгоритмы.
Модель Gather Sum Apply Это также итеративная модель. Ее особенность заключается в том, что пользовательский код запускается не относительно вершин, а относительно ребер. Она включает три фазы.
• Gather – выполнение алгоритма относительно ребра и отправка сообщений в смежные вершинам ребра.
• Sum – каждая вершина производит агрегацию поступивших сообщений.
• Apply – обновление вершины....
HyperX Ближайшим аналогом описанной нами системы является проект HyperX. Это надстройка для платформы Apache Spark для обработки гиперграфов. В этой системе используются собственный алгоритм распределения по кластеру и модифицированная модель Pregel. Авторы HyperX рассматривали вариант приведения гиперграфа к плоскому графу, но выбрали вариант с хранением гиперграфа без преобразований. Данный подход возможен в случае гиперграфа, но не в случае метаграфа, поскольку гиперграфовая модель не предполагает вложенности.
Выводы и дальнейшие направления работы В данной статье рассмотрен подход к реализации метаграфовых агентов, позволяющих осуществлять полноценную обработку метаграфовых моделей, на основе технологий обработки больших данных и больших графов. Мы рассмотрели возможные архитектуру системе по обработке метаграфов с помощью технологий больших данных. Также были рассмотрены основные методы распределения и обработки графов применительно к метаграфам. Для подтверждения предположений о целесообразности различных подходов мы планируем проведение экспериментов на метаграфах различной конфигурации.
Список литературы
1. Черненький В.М., Гапанюк Ю.Е., Ревунков Г.И., Терехов В.И., Каганов Ю.Т. Метаграфовый подход для описания гибридных интеллектуальных информационных систем // Прикладная информатика. 2017. Т. 12. № 3 (69). С. 57–79.
2. Chernenkiy V., Gapanyuk Yu., Terekhov V., Revunkov G., Kaganov Yu. The hybrid intelligent information system approach as the basis for cognitive architecture // Procedia Computer Science. 2018. Vol. 145. P. 143–152.
3. Chernenkiy V., Gapanyuk Yu., Nardid A., Todosiev N. The Implementation of Metagraph Agents Based on Functional Reactive Programming // 26th Conference of Open Innovations Association (FRUCT). Yaroslavl, Russia. 2020. P. 1–8. DOI: 10.23919/FRUCT 48808.2020.9087470
4. Dunin I.V., Chernenkiy V.M., Gapanyuk Yu.E., Kaganov Yu.T., Lyaskovsky M.A., Larionov V.S. Storing Metagraph Model in Relational, Document-Oriented, and Graph Databases // Selected Papers of the XX International Conference on Data Analytics and Management in Data Intensive Domains (DAMDID/RCDL 2018). 2018. P. 82–89.
5. Gonzalez J.E., Low Y., Gu H., Bickson D., Guestrin C. Powergraph: Distributed graphparallel computation on natural graphs // Proc. of Symposium on Operating Systems Design and Implementation (OSDI). USENIX. 2012.
СПОСОБ ХРАНЕНИЯ МЕТАГРАФОВОЙ МОДЕЛИ ДАННЫХ В СУБД POSTGRESQL
Список литературы
1. Basu A., Blanning R.W. Metagraphs and their applications. Springer. 2007. 172 p.
2. Черненький В.М., Гапанюк Ю.Е., Ревунков Г.И., Терехов В.И., Каганов Ю.Т. Метаграфовый подход для описания гибридных интеллектуальных информационных систем // Прикладная информатика. 2017. Т. 12. № 3 (69). С. 57–79.
3. Самохвалов Э.Н., Ревунков Г.И., Гапанюк Ю.Е. Использование метаграфов для описания семантики и прагматики информационных систем // Вестник Московского государственного технического университета им. Н.Э. Баумана. Сер. Приборостроение. 2015. № 1 (100). С. 83–99.
4. Гапанюк Ю.Е., Ревунков Г.И., Федоренко Ю.С. Предикатное описание метаграфовой модели данных // Информационно-измерительные и управляющие системы. 2016. № 12. С. 122–131. 5. Гапанюк Ю.Е., Ерохин И.А., Белоусов Е.А. Метаграфовое описание семантики изображения // Естественные и технические науки. 2021. № 7. С. 179–182.
ОПИСАНИЕ МЕТАГРАФА ОЗЕРА ДАННЫХ И РАЗРАБОТКА АЛГОРИТМА ПОИСКА ПУТИ ДО ВЕРШИНЫ ...