Cypher-запрос для сопоставления сильных двусторонних отношений и фильтрации по значениям свойств в Neo4j

Я хотел бы найти в Neo4j DB подграф только с сильными двусторонними отношениями.

Скажем, отношение ЛЮБОВЬ, а атрибут - Поцелуи, тогда я хотел бы найти только подграф, в котором обе стороны поцеловали друг друга более 2 раз.

START n=node(*)
MATCH n-[r1:LOVES]->friend<-[r2:LOVES]-n
WHERE r1.Kisses > 2 and r2.Kisses > 2
RETURN n, friend, r1, r2
LIMIT 20

проблема в том, что запрос, кажется, выполняется вечно на графике взаимосвязей узлов 3M и 30M, на 32 ГБ ОЗУ, четырехъядерной системе с максимальной кучей 16 ГБ для neo4j (калькулятор neo4j предложил 8 ГБ).

Подозреваю, где-то скрывается бесконечная петля.

ОС: Ubuntu 12.04.1 LTS-сервер

Софт: neo4j-community-1.8.1

версия java "1.7.0_10" (neo4j start говорит, что нужно использовать JDK6)

Среда выполнения Java (TM) SE (сборка 1.7.0_10-b18)

64-разрядная серверная виртуальная машина Java HotSpot (TM) (сборка 23.6-b04, смешанный режим)

РЕДАКТИРОВАТЬ: совпадение неверно, оно должно быть

MATCH n-[r1:LOVES]->friend-[r2:LOVES]->n

ОБНОВЛЕНИЕ: после исправления семантики выше я все еще не могу получить полный результат за 5 минут.

ЛЮБОВЬ - единственный тип отношений, и около 10-20% отношений имеют соответствующий другой тип отношений.

Моя конечная цель - найти подходящие значения Kiss, чтобы у меня осталось ‹100k узлов (и все соответствующие отношения LOVES) и я мог экспортировать этот подграф.

Вот псевдокод алгоритма того, что я пытаюсь сделать:

let E be edge.list to be processed
let myedgelist be empty list
for e in E:
  if e.n1 > e.n2: # so we do not look twice
    continue
  if not exist(e[n2][n1]): # this is where lookup can be a problem O(1) for hash, O(logn) for sorted, O(n) for something random)
    continue
  if e.kisses > 2 and e[n2][n1].kisses > 2:
    add e to myedgelist
    add e[n2][n1] to myedgelist
return myedgelist

Этот алгоритм должен работать не более, чем edgecount * log (edgecount), если только нет эффективного способа найти наличие обратной связи в neo4j, что могло бы показаться довольно немыслимым.


nosql database neo4j cypher
person Sint    schedule 04.01.2013    source источник
comment
Ваше предложение MATCH не должно быть таким, как в console.neo4j.org/?id=yuv3nx ?   -  person Werner Kvalem Vesterås    schedule 04.01.2013
comment
Вы совершенно правы!   -  person Sint    schedule 04.01.2013
comment
Он все еще работает вечно?   -  person Werner Kvalem Vesterås    schedule 04.01.2013
comment
Хорошо с LIMIT 20 и низким порогом поцелуев, как в ›2, это завершается за несколько минут.   -  person Sint    schedule 04.01.2013
comment
у вас эти 30 миллионов отношений построены только на типе ЛЮБОВЬ?   -  person ulkas    schedule 04.01.2013
comment
Однако без ОГРАНИЧЕНИЯ и высокого порога, как в поцелуях ›100, кажется, что он снова будет работать вечно. Несколько результатов - это не то, что мне нужно. В конечном итоге я хочу экспортировать подграф.   -  person Sint    schedule 04.01.2013
comment
Да, только ЛЮБОВЬ, по моим оценкам, примерно в 20% случаев ЛЮБОВЬ идет в обе стороны.   -  person Sint    schedule 04.01.2013
comment
Я думаю, что neo4j в этом случае не идеальный db. он практически не имеет ничего общего с алгоритмами графа, поскольку запрос практически сравнивает значения вручную слишком много раз - около 10 миллионов операций. может помочь фильтр типов rel - например, создать отношения для любого количества поцелуев - LOVES1 для 1 поцелуя, LOVES2 для 2 поцелуев .... надеюсь, ваши пользователи не целуют друг друга более 2 ^ 16 раз. затем MATCH n-[r1:LOVES2]->friend-[r2:LOVES2]->n   -  person ulkas    schedule 04.01.2013
comment
Что ж, идея состоит в том, чтобы получить меньший подграф из Neo4j во что-то, что имеет множество алгоритмов графов (Gephi, Networkx, Igraph и др.). Networkx ужасно работает с 30M ребрами ...   -  person Sint    schedule 04.01.2013

Ответы (2)


arrow_upward
1
arrow_downward

Можете ли вы попробовать сделать friend целевым узлом

START friend=node(*)
MATCH n-[r1:LOVES]->friend-[r2:LOVES]->n
WHERE r1.Kisses > 2 and r2.Kisses > 2
RETURN n, friend, r1, r2
LIMIT 20

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

START n=node(*)
MATCH n-[r1:LOVES]->friend
WHERE r1.Kisses > 2
WITH n,r1,friend
MATCH n<-[r2:LOVES]-friend
WHERE r2.Kisses > 2
RETURN n, friend, r1, r2
LIMIT 20

или, в качестве альтернативы, только половина запроса с совпадением, а вторая половина с фильтром

START n=node(*) 
MATCH n-[r1:LOVES]->friend 
WHERE r1.Kisses > 2 
 AND ALL(r2 in extract(
              p in friend-[:LOVES]->n : head(rels(p))) 
         WHERE r2.Kisses > 2) 
RETURN n, friend, r1
LIMIT 20

вот консоль для проверки запросов: http://console.neo4j.org/r/tqvb1p

Но в конце концов вы обрабатываете 3M узлов с совпадением, которое потенциально может взорвать до 3M ^ 2

person Michael Hunger    schedule 04.01.2013
comment
Второй подход примерно в 10 раз быстрее, чем первый (и мой оригинальный тоже) !! - person Sint; 05.01.2013
comment
Тем не менее, должен быть способ избежать использования 3M ^ 2, поскольку мой алгоритм, реализованный на неоптимизированном Python с простым словарем, делает то же самое примерно за 60 секунд. Сложность этого фильтра действительно должна быть равна E. Должен ли я отказаться от Сайфера и попробовать Гремлин? - person Sint; 08.01.2013

arrow_upward
1
arrow_downward

Вы должны попробовать это в версии 1.9 - средство сопоставления шифров было значительно оптимизировано для этого типа запросов. Хотя было бы неплохо избежать узла (*). Все ли ваши узлы люди? В противном случае вы можете выполнить запрос индекса, чтобы получить только соответствующие узлы лиц.

start n=node:people("name:*")...

person Eve Freeman    schedule 04.01.2013