1

大規模な二部有向グラフ データセット (約 2000 万要素) があります。現在の使用では、1 回の実行で最大 500,000 ノードに到達するトラバーサル アルゴリズムを実行しています。アルゴリズムは機能しますが、これまではテキスト ファイルからメモリに読み込まれたデータが不足していました。

テキストファイルは悪いアプローチのように見えるので、データを隣接リストとしてmongoDBに転送しました。

{ _id: 1, children: [2, 3] }
{ _id: 2, children: [4] }
{ _id: 3, children: [5, 6, 7] }

これは機能しますが、私がやっていることに対してモデルが非効率的であるように感じます。疑似コードでは、_ id: 1から始まる幅優先検索のクエリ構造は次のようになります。

children = getChildren(_id = 1)
for child in children
    grandchildren = getChildren(_id = child)
    // etc., either recursively or as a nested loop

私がデータベースで抱えている問題は、ノードを接続するロジックがないことです。すべてのクエリはインデックス ツリーをトラバースする必要があります。私の間違いでなければ、これは O(log N) です。テキスト ファイルのアプローチは、ロード後の O(1) です。ノードの子を直接指す簡単なルックアップ ルールをいくつか作成できるからです。

TL;DRデータベースを使用して O(1) 時間で大規模なネットワークを横断する方法はありますか?

4

2 に答える 2

2

NoSQLグラフデータベースであるNeo4Jを使用してみることができます。使ったことはありませんが、高性能を約束します。

于 2012-05-21T16:35:25.317 に答える
0

MongoDB は多目的データベースではありません。専用の専用グラフ データベースの使用に関心があることは明らかです。このようなグラフや関連する検索アルゴリズムに MongoDB を使用することはできません。

于 2012-05-21T17:36:31.813 に答える