3

Neo4j DB で強い双方向関係のみを持つサブグラフを見つけたいと思います。

関係がLOVESで、属性がKissesであるとしましょう。両方が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 リレーションシップ グラフ、32GB RAM、neo4j の最大ヒープが 16GB のクアッド コア システム (neo4j 計算機は 8GB を推奨) で永久に実行されるように見えることです。

どこかに無限ループが隠れているのではないかと思います。

OS: 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)

Java HotSpot(TM) 64 ビット サーバー VM (ビルド 23.6-b04、混合モード)

編集：一致は正しくありません

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

更新: 上記のセマンティクスを修正した後も、5 分で完全な結果を得ることができません。

LOVES は唯一の関係タイプであり、約 10 ～ 20% の関係では、対応する関係が逆になります。

私の最終的な目標は、適切な Kiss の値を見つけて、100,000 個未満のノード (およびすべての適切な 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 で逆関係の存在を検索する効果的な方法がない場合は、かなり考えられないように思われます。

4

2 に答える 2

1

You should try this in 1.9--the cypher matcher has been optimized significantly for this type of query. Although it would be nice to avoid the node(*). Are all of your nodes people? If not you might want to do an index query to only get the relevant person nodes.

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

于 2013-01-04T16:47:49.037 に答える
1

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

試合を 2 つの部分に分割することができます

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 ^ 2 まで爆発する可能性のある一致で 3M ノードを処理しています。

于 2013-01-04T18:18:04.750 に答える