Поиск паттернов анализа ссылок - PullRequest
Новая
       17

Поиск паттернов анализа ссылок

1 голос
/ 03 февраля 2012

Описание проблемы

Я реализую алгоритм анализа ссылок на огромной базе данных графа.

База данных графа состоит из сущностей (вершин) и отношений(ребра).

Каждый тип сущности имеет свойства.Например, Персона: [возраст, рост, вес] .

Каждое отношение также имеет свойства: Например, Вызов (телефон, телефон): [дата, продолжительность] или Own (Person, Phone): [дата начала, дата окончания].

Теперь мне дан шаблон со следующей структурой:

[тип объекта,ограничения] [тип отношения, ограничения] [тип объекта, ограничения] [тип отношения, ограничения] ... [тип объекта, ограничения]

Например:

[человек, возраст> 20] [свой, дата начала> 01.01.2010] [телефон, заканчивается на «5»] [дата звонка> 01.01.2010] [телефон, начинается на «6'] [принадлежит, дата начала <1/2/2011] [person, height> 40] .

Мне нужно найти ВСЕ действительные назначения для всех сущностей и отношений в шаблоне.

Я могу запросить базу данных, используя следующие примитивы:

  • Найти первые 1000 [тип объекта, тип отношения, тип объекта] назначения дляданный набор ограничений.
  • Найти следующую 1000 длявышеуказанные
  • Найти первые [конкретные сущности, отношения типа, сущности типа] назначения для данного набора ограничений.
  • Найти следующие 1000 для вышеупомянутых

Сохранение всех ответов на данный запрос в оперативной памяти невозможно.Может быть миллионы (миллиарды?) Назначений для каждой тройки сущность-связь-сущность.Тем не менее, число назначений для всего шаблона предполагается небольшим.

Что я пробовал:

Для цепочки ET1-RT1-ET2-RT2-ET3-RT3 ... Наивной реализацией будет: 

Get first 1000 (ET1-RT1-ET2)   
for each concrete ET2:
    Get first 1000 (ET2-RT2-ET3)
        for each concrete ET3:
            ...

Проблема в том, что я могу решать одни и те же подзадачи более одного раза.

IЯ ищу алгоритм, который устраняет такие избыточности, который также экономит память.

Примечание:

Я ищу алгоритм.Не для ответа, такого как «Использовать SQL JOIN» / «Использовать SPARQL» ...

1 Ответ

0 голосов
/ 03 февраля 2012

Динамическое программирование должно быть полезным здесь.

Упростим правила как R1-R2-R3 ... Rk здесь.

Пусть next_nodes (узел x, правило R) возвращает все связанные узлы x, которые соответствуют правилуR. Если R - ограничение сущности: оно возвращает одноэлементное множество одного и того же узла, если условие выполнено, иначе пустое множество.Для реляционного ограничения он возвращает все связанные узлы, которые удовлетворяют условию. 

Initialize cur_set to all set of nodes.

nextset = {}

For each rule R in Ri:
    for each node x in cur_set:
        nextset = nextset U next_nodes(x)
    cur_set = nextset

Вы должны иметь возможность хранить набор в виде хеш-таблицы или дерева (любой журнал (n) структура данных времени поиска и обновления).

Хотя я пропустил ту часть, где вы держите путь прохождения, это должно быть довольно легко сделать.Для каждого элемента в наборе добавьте атрибут с именем «путь» и добавляйте текущий узел на каждой итерации.Обратите внимание, что несколько путей могут привести к одному и тому же промежуточному / конечному узлу.

...