3

こんにちは私はNeo4j用のDBSCANアルゴリズムを実装しようとしていますが、深刻なパフォーマンスのボトルネックに直面しています。実装について説明してから、助けを求めます。

1つのクエリですべてのコアノードを取得できるように、可能なイプシロン値を離散化し、各ノードの各離散化の下にあるネイバーの数をカウントしました。

START a = node(*)
WHERE a.rel<cutoff threshold>! >= {minp}
RETURN a

この部分は高速ですが、高速でない部分はフォローアップクエリです：

START a = node({i})
SET a.label<cutoff threshold>_<minpoints> = {clust}
WITH a
MATCH a -[:'|'.join(<valid distance relations>)]- (x)
WHERE not(has(x.label<cutoff threshold>_<minpoints>))
WITH x
SET x.label<cutoff threshold>_<minpoints>={clust}
RETURN x

次に、開始するコアノードを選択し、コアノードのネイバーがまだ存在する限り、上記のクエリを実行してネイバーにラベルを付けます。

問題は、私のグラフのスパース性のレベルが非常に異なることだと思います。類似性が弱いことから始めて、ほぼ完全に接続されており、ノード間で約5,000万の関係がありますが、類似性が高い場合は、約10,000の間にわずか20kの関係があります。ノード（またはそれ以下）。何があっても、それは常に本当に遅いです。これを処理するための最良の方法は何ですか？関係タイプと開始ノードのインデックスを作成するのですか？この問題に関するリソースを見つけることができませんでした。驚くべきことに、これはかなり標準的なグラフアルゴリズムであるため、実装はまだありません。scikit.learnを使用することもできますが、メモリ内の距離行列のみに制限されます:(

4

2 に答える 2

0

インデックスを使用するDBSCAN実装があります。私はについて知らないので、あなたのアプローチが効率的かどうかは本当にわかりません。事前計算が必要になる可能性があるのは、実際にはグラフのスパースバージョンであり、イプシロンのしきい値内にあるエッジのみが含まれています。

明らかにデータセットの密度が異なることを指摘したいので、代わりにOPTICSを使用することをお勧めします。これはDBSCANのバリアントであり、イプシロンパラメーターを廃止します（区別する必要もありません）。すべてのノードが特定のイプシロンのコアノードであるため、「コア」ノード）。Wekaバージョン（または浮かんでいるwekaに触発されたPythonバージョン）は使用しないでください。それらは、半分がOPTICSで半分がDBSCANです。

効率的にソートされた更新可能なヒープが利用できる場合、OPTICSはかなり高速になります。

于 2012-09-28T06:18:53.717 に答える
0

どのバージョンのneo4jでこれを試しましたか？

1.8までは、パフォーマンスは暗号（言語ではなく）の設計目標ではありませんでした。最近のスナップショット（1.9-SNAP）を見てください。

また、ホットデータセットがディスクからロードされるだけでなく（そうでない場合はdisk-ioを測定する）、メモリマップ設定とJVMヒープが十分に大きいことを確認してください。

また、メモリフットプリントが小さいNeo4jエンタープライズのGCRキャッシュを確認することもできます。

count(x)クエリのカーディナリティは何ですか？小さすぎると、実行中の小さなトランザクションが多すぎます。実行するPython組み込みまたはRESTのどちらを使用するかに応じて、より大きなtx-scopeまたはREST-batch-operationsを使用します

あなたはすでに素晴らしいパラメータを使用しています。あなたのrel-typesの変動性は何ですか？

データセット/ジェネレーターとコードを私たち（Neo4j）と共有して、私たちの側でパフォーマンステストを行う機会はありますか？

于 2012-09-28T15:31:20.800 に答える