1

私はしばらくの間、Neo4j 1.9.M03 を評価してきましたが、予期していなかったような結果になりました。

〜140,000頂点のグラフがあります。また、エッジには 3 つのクラスがあります。これらを父、母、夫と呼びましょう。クラスごとに約 80,000 のエッジがあります。プロパティもインデックスもありません。頂点ストアのサイズは約 1.3 MB、エッジ ストアのサイズは約 8 MB です。

データは SQL Server に由来し、SQL から Neo4j への移行の品質は正しいことが知られています。SQL 最短パス ストアド プロシージャは、数十の頂点ペアに対して実行され、最短パスの距離とパスがわかっています。

最短パス クエリは Cypher です。START one=node(0), two=node(1234) MATCH p = shortestPath(one-[*..1000]-two) RETURN p;

部分的なテスト ケース 1:私は夫と父の関係のみを使用し、サイクルの発生 (例:v[0] -> v[1] -> v[2] -> v[0])低い。特定の既知の長いパス (例: ~450 ホップであることがわかっている) で最短パス計算を実行すると、50ms 以内に返されます (キャッシュされていない) ~550 ホップのパス. エッジの一部を除外しているため、長さが増加することが予想されます.

部分的なテスト ケース 2 : 同様に、夫と母の関係のみを使用する場合、サイクルの発生 (たとえばv[0] -> v[1] -> v[2] -> v[0])、低いです。同じ最短パスを実行すると、前と同じ順序で結果が得られます: 約 50 ミリ秒 (非キャッシュ) )、経路長も同様に増加します。

完全なテスト ケース: 私はすべての関係 (父、母、夫) を使用します。一般的なケースのため、サイクルの発生率は予想通り高くなりましたv[0] mother-> v[1] husband-> v[2] <-father v[0]。最短パス クエリを実行すると、JVM が 4 ギガバイトのメモリを割り当て、計算が完了しません。これが問題です。

私の論文は、サイクルの定期的な発生がこの動作を引き起こしているということです。そうでなければ、最短パスアルゴリズムがサイクルを考慮していない限り、親エッジの別のクラスを追加するだけで、パフォーマンスにそれほど大きな違いはないと思います。

Java API を直接使用して Dijkstra アルゴリズムを適用し、すべてのエッジでコストを 1 に設定し、使用した標準の ShortestPath アルゴリズムと同様の結果を達成しました。その結果、IntelliJ デバッグ時間の 6 分後にこの例外を受け取りました。

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
    at org.neo4j.kernel.impl.util.RelIdArray$RelIdIteratorImpl.<init>(RelIdArray.java:661)
    at org.neo4j.kernel.impl.util.RelIdArray$DirectionWrapper$3.iterator(RelIdArray.java:327)
    at org.neo4j.kernel.impl.util.RelIdArray.iterator(RelIdArray.java:270)
    at org.neo4j.kernel.impl.core.NodeImpl.getAllRelationships(NodeImpl.java:172)
    at org.neo4j.kernel.impl.core.NodeImpl.getRelationships(NodeImpl.java:270)
    at org.neo4j.kernel.impl.core.NodeProxy.getRelationships(NodeProxy.java:82)
    at org.neo4j.kernel.StandardExpander$AllExpander.doExpand(StandardExpander.java:303)
    at org.neo4j.kernel.StandardExpander$RelationshipExpansion.iterator(StandardExpander.java:194)
    at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.expandRelationshipsWithoutChecks(TraversalBranchImpl.java:114)
    at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.expandRelationships(TraversalBranchImpl.java:104)
    at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.initialize(TraversalBranchImpl.java:130)
    at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.next(TraversalBranchImpl.java:150)
    at org.neo4j.graphalgo.impl.util.BestFirstSelectorFactory$BestFirstSelector.next(BestFirstSelectorFactory.java:73)
    at org.neo4j.kernel.impl.traversal.TraverserIterator.fetchNextOrNull(TraverserIterator.java:65)
    at org.neo4j.kernel.impl.traversal.TraverserIterator.fetchNextOrNull(TraverserIterator.java:34)
    at org.neo4j.helpers.collection.PrefetchingIterator.hasNext(PrefetchingIterator.java:55)
    at org.neo4j.graphalgo.impl.util.StopAfterWeightIterator.fetchNextOrNull(StopAfterWeightIterator.java:45)
    at org.neo4j.graphalgo.impl.util.StopAfterWeightIterator.fetchNextOrNull(StopAfterWeightIterator.java:29)
    at org.neo4j.helpers.collection.PrefetchingIterator.hasNext(PrefetchingIterator.java:55)
    at org.neo4j.helpers.collection.IteratorUtil.firstOrNull(IteratorUtil.java:51)
    at org.neo4j.helpers.collection.IteratorUtil.firstOrNull(IteratorUtil.java:201)
    at org.neo4j.graphalgo.impl.path.Dijkstra.findSinglePath(Dijkstra.java:98)
    at org.neo4j.graphalgo.impl.path.Dijkstra.findSinglePath(Dijkstra.java:50)
    at ShortestPathCalc.Dijkstra(Main.java:198)
    at Main.main(Main.java:53)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:601)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)

私が正しいと思いますか？これは、グラフ データベースまたはその最短パス アルゴリズムの既知の制限ですか? 以前に訪れた頂点がハッシュ テーブルに格納されないというのは、非常にばかげているように思えます。そのため、最短パス アルゴリズムは、以前に訪れた頂点からのパスを 2 回以上試行しません。

2013 年 1 月 25 日更新

フォローできるように Github リポジトリを作成してください。

https://github.com/squirrelsama/neo4j-shortestpath-issue

2013 年 2 月 7 日更新

受け入れられた回答を参照してください。要するに、サイクルはそれとは何の関係もありません。

4

2 に答える 2

1

ノード44715と17173の間の最短パスを取得しようとすると、その最短パスは112ホップであることがわかっているため、問題を観察できます。

最短パスの評価を111ホップに制限すると、クエリは非常に高速に完了しますが、パスはありません。START one=node(44715), two=node(17173) MATCH p = shortestPath(one-[*..111]-two) RETURN p;

ただし、最短パスの評価を112ホップに制限すると、クエリの完了に失敗し、JVMが最大4ギガバイトのメモリを迅速に割り当てます。START one=node(44715), two=node(17173) MATCH p = shortestPath(one-[*..112]-two) RETURN p;

Neoは、これが返されるPathオブジェクトのアセンブリに関連するエッジケースのバグであることを確認しました。それは彼らのバグバックログにあります。

言い換えれば、サイクルは問題とは何の関係もありません。

于 2013-02-08T03:08:01.553 に答える
1

neo4j トラバーサル フレームワークを使用すると、トラバーサルで使用する一意性を選択できます。たとえば、RELATIONSHIP_GLOBAL を使用すると、トラバーサル中にリレーションシップを 1 回だけトラバースすることができます。それはあなたの問題を解決するかもしれません：

// 単方向
Traversal.traversal( Uniqueness.RELATIONSHIP_GLOBAL )
         .evaluator( Evaluators.returnWhereEndNodeIs( myEndNode )
         .traverse( myStartNode );

// 双方向
Traversal.bidirectionalTraversal()
         .mirroredSides( Traversal.traversal( Uniqueness.RELATIONSHIP_GLOBAL ) )
         .traverse( myStartNode, myEndNode );

上記の例は原則であり、クエリで動作するように変更する必要がある場合があります。

于 2013-01-27T21:02:27.893 に答える