Как эффективно хранить и извлекать крупномасштабные графические данные?

искусственный интеллект

Аннотация: В этой статье кратко представлены знания, связанные с хранением и поиском графов знаний.

Эта статья опубликована в сообществе HUAWEI CLOUD.«Хранение и извлечение графа знаний», оригинальный автор: JuTzungKuei.

1 Обзор

Предыстория: С развитием и популяризацией Интернета складывается мир, в котором все взаимосвязано. В то же время данные растут в геометрической прогрессии, и мы находимся в новой эре стремительного роста цифровых торрентов.

Сколько данных мы генерируем каждый день? По статистике каждый день:

  • Отправьте блогу 500 миллионов твитов;

  • отправлено 294 миллиарда электронных писем;

  • Ежедневно в мире выполняется 5 миллиардов поисковых запросов в Интернете;

  • Подключенный автомобиль генерирует 4 ТБ данных;

  • Facebook генерирует 4 ПБ данных каждый день, включая 350 миллионов фотографий и 100 миллионов часов видео.

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

  • В DBpedia около 80 миллионов троек;

  • YAGO имеет более 120 миллионов троек;

  • В Викиданных почти 410 миллионов троек;

  • Freebase имеет более 3 миллиардов троек;

  • Китайская энциклопедия насчитывает около 140 миллионов троек.

Итак, как мы можем эффективно хранить и извлекать крупномасштабные графические данные? ? ?

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

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

  • Понятия: Люди, Страны, Фильмы и т.д.

  • Сущность: Энди Лау, Чжу Лицянь, Китай, Мир без воров и т. д.

  • Атрибуты: рост, вес, пол, заглавная буква, аббревиатура, время выпуска, оценка Дубана и т. д.

  • Отношения: жена, дочь, национальность, главные роли и т.д.

2. Хранение графа знаний

Знание в графе знаний представлено структурой RDF, а его базовой единицей является факт.

Каждый факт представляет собой тройку: , где:

  • Тема с: Да, сущности, события, концепции

  • Предикат P: может быть отношением, атрибутом

  • Объект O: может быть сущностью, событием, концепцией, общей ценностью.

Ниже показан список троек для представления знаний в графе знаний.

<S, P, O>

. . . . . .

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

2.1. Хранение на основе табличной структуры

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

2.1.1 Тройная таблица

Факты в графе знаний являются тройками.Простым и прямым методом хранения является разработка таблицы для хранения всех фактов в графе знаний, то есть построение таблицы с тремя столбцами в реляционной базе данных.Схема таблицы есть: . Сохраните каждую тройку в графе знаний как строку в таблице троек.

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

Представители схемы: система баз данных RDF 3store, Virtuoso

2.1.2 Лист свойств

Таблица атрибутов, также известная как таблица типов, предназначена для построения таблицы для каждого типа, и экземпляры одного и того же типа помещаются в одну и ту же таблицу. Каждый столбец таблицы представляет атрибут объекта этого типа, а каждая строка хранит экземпляр объекта этого типа.

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

Представитель схемы: тройная библиотека RDF Jena

фигура

нация

Кино

2.1.3 Таблица уровней

Каждая строка таблицы уровня записывает все предикаты и объекты субъекта в графе знаний. Фактически таблица уровней эквивалентна списку смежности графа знаний. Количество столбцов в горизонтальной таблице — это количество различных предикатов в графе знаний, а количество строк — это количество различных субъектов в графе знаний.

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

Представитель схемы: DLDB, ранняя система баз данных RDF.

2.1.4 Вертикальный стол

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

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

Представитель программы: SW-Store

Пол

в главных ролях

капитал

2.1.5 Полный индекс

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

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

Представители программы: RDF-3X, Hexastore

Шесть столов: СПО, СОП, ПСО, ПОС, ОСП, ОПС

2.2. Хранение на основе графовой структуры

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

2.2.1 Список смежности

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

2.2.2, матрица смежности

Так называемая матрица смежности предназначена для поддержки в компьютере нескольких n x n-мерных матриц, где n — количество узлов в графе знаний. Каждая матрица соответствует предикату, где каждая строка или столбец соответствует узлу в графе знаний. Если i-я строка и j-й столбец матрицы, соответствующие предикату p, равны 1, это означает, что существует ребро с предикатом p из i-го узла в j-й узел в графе знаний .

Трехмерная матрица M: |S|x|P|x|O|, которые соответственно представляют количество подлежащего, сказуемого и объекта.Если существует в графе знаний, то M[i][ j][k]= 1, в противном случае устанавливается в 0.

2.2.3, графическая база данных

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

  • Узел: представляет такие объекты, как сущности, события и т. д.

  • Край: относится к направленной линии, соединяющей узлы в графе, используемой для представления отношений между различными узлами.

  • Атрибуты: описывают свойства узла или ребра.

  • Распространенные графовые базы данных: Neo4J, JanusGraph, OrientDB и др.;

3. Поиск графа знаний

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

3.1 SQL

Язык структурированных запросов Язык структурированных запросов для управления реляционными базами данных.

четыре операции

  • Добавлено: вставлять в имя таблицы (столбец 1, столбец 2, ...) значения (значение 1, значение 2, ...)

  • Удалить: удалить из таблицы имя, где условие

  • Изменение: столбец набора имени таблицы обновления 1 = значение 1, где условие

  • Проверить: выбрать столбец 1, столбец 2, ... из имени таблицы, где условие

3.2 SPARQL

SPARQL — это язык запросов и протокол сбора данных, разработанный W3C для данных RDF, и этот язык запросов широко поддерживается графовыми базами данных.

Три операции:

  • Добавлено: вставка тройных данных

  • Удалить: удалить тройные данные

  • Модификация: Нет, в сочетании с дополнениями и исключениями

  • Проверить: выбрать переменную 1, переменную 2, ... где режим графика

    выберите ?x, ?y где { Мир без воров с участием ?x. Адские дела с ?x в главной роли. ?x день рождения ?y . }

скопировать код

3.3 Gremlim

Gremll - это диаграмма траверсального языка, используемого в Framework TinkerPOP Apache. Используя Gremll, вы можете легко запросить данные графа, изменять графики, выполнять локальные обходные и фильтрующие атрибуты.

три операции

  • Добавлено: g.addV('персонаж').property(id,'007').property('день рождения','22 июня 1962'), g.addE('муж').property('xxx' , ' гггг').от(gV('001')).до(gV('002'))

  • Удалить: g.V('007').drop()

  • Проверить: g.V().hasLabel('character'), g.E().label(), g.V().valueMap()

3.4 Cypher

Cypher — это язык запросов к описательным графам, который позволяет выполнять выразительные и эффективные запросы к хранилищу графов без необходимости написания кода обхода структуры графа. — широко используемый язык запросов к базе данных с декларативным графом.

четыре операции

  • Добавить: создать (n: персонаж {имя: «Чжоу Синчи», день рождения: «22 июня 1962 г.»}) return n;

  • Удалить: match(s:Student{id: 1}) отделить удалить s;

  • Изменение: match(n) где id(n)=7 set n.name = 'neo' return n;

  • Проверить: match(n{name:"Энди Лау"}) return n, match(a:Character{name:"Andy Lau"})-[b:Relation {{name:"Nationality"}]->(c) вернуть с;

Ссылаться на

Нажмите «Подписаться», чтобы впервые узнать о новых технологиях HUAWEI CLOUD~

Категории