Поиск по шаблону анализа ссылок

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

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

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

У каждого типа сущности есть свойства. Например, Человек: [возраст, рост, вес].

Каждая связь также имеет свойства: например, Звонок(Телефон,Телефон) : [дата, продолжительность] или Собственное(Человек, Телефон) : [дата начала, дата окончания].

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

[тип-сущности,ограничения] [тип-отношения,ограничения] [тип-сущности,ограничения] [тип-отношения,ограничения] ... [тип-сущности,ограничения]

Например:

[человек,возраст>20] [собственный, дата начала>1/01/2010] [телефон, заканчивается на "5"] [дата звонка>1/1/2010] [телефон, начинается на "6" ] [владелец, дата начала‹02.01.2011] [человек, рост>40].

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

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

  • Найдите первые 1000 назначений [entity-type,relationship-type,entity-type] для заданного набора ограничений.
  • Найдите следующие 1000 для вышеуказанного
  • Найдите первые назначения [concrete-entity,relationship-type,entity-type] для заданного набора ограничений.
  • Найдите следующие 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:
            ...

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

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

Примечание:

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


algorithm graph-databases social-networking graph-algorithm
person Lior Kogan    schedule 02.02.2012    source источник
comment
Не уверен насчет алгоритма, но думали ли вы просто запомнить результаты подзадач.   -  person Gerrat    schedule 03.02.2012
comment
посмотреть на уменьшение карты; Я хотел бы иметь хорошую ссылку для вас   -  person Adrian    schedule 03.02.2012
comment
@Gerrat: Боюсь, наивная таблица поиска будет слишком большой. Мне нужно что-то более изощренное здесь.   -  person Lior Kogan    schedule 03.02.2012

Ответы (1)


arrow_upward
0
arrow_downward

Здесь может помочь динамическое программирование.

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

Пусть next_nodes(node ​​x, Rule 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)).

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

person ElKamina    schedule 02.02.2012
comment
Этот метод будет хранить только пути, для которых были выполнены условия. Он переоценит ошибочные пути (а это большинство путей). Это также может потребовать огромного временного хранилища. - person Lior Kogan; 03.02.2012
comment
@LiorKogan Вам нужны только пути, которые удовлетворяют условиям, верно? Он не будет переоценивать неудачные пути (каждое условие проверяется на узле не более одного раза). Да, для этого требуется большое пространство. - person ElKamina; 03.02.2012