7

現在、約1,000 万のノードと3,500 万のエッジを持つグラフがあります。今のところ、プログラムの開始時に完全なグラフがメモリにロードされます。これには数分かかり (結局のところ Java です)、約 0.5 ギガバイトの RAM が必要です。今のところ、デュアル コア プロセッサと 4 ギガバイトの RAM を搭載したマシンで動作します。

幅優先検索を使用してグラフを検索すると、メモリ使用量が 1 ギガバイトのピークに達し、平均で 10 秒かかります。

プログラムを数台のコンピューターに展開したいと考えています。グラフ検索以外の機能は、ほとんどリソースを消費しません。私のターゲット システムは非常に小型で、512 メガバイトの RAM しかありません。

メモリをあまり消費せずにそのグラフを検索するための方法を (おそらくデータベースを使用して) 実装する方法に関する提案はありますか? プログラムはハードウェア デバイスにアクセスしているため、ほとんどの場合アイドル状態であるため、上記のグラフのパス検索には最大で約 5 分かかる場合があります...

私の方向に投げかけられた考えに感謝します。

アップデート：

neo4jが見つかりました。この種の巨大なグラフに適しているかどうかは誰にもわかりませんか?

4

3 に答える 3

8

あなたの質問は少しあいまいですが、一般的に、深さ優先検索と同じ量のメモリを使用しながら幅優先セマンティクスにほぼ従う良い戦略はIterative Deepeningです。アイデアは、最初は 1 レベルに制限された深さ優先検索を行うことです。それでも解決策が見つからない場合は、ゼロから始めて 2 レベルに制限します。それが失敗した場合は、3 つのレベルを試してください。

これは最初は少し冗長に思えるかもしれませんが、深さ優先検索を行っているため、メモリ内に保持するノードがはるかに少なくなり、単純な幅優先検索よりも常に 1 つ少ないレベルで検索します。レベル内のノードの量は指数関数的に増加するため、より大きなグラフでは、最後の余分なレベルを 1 つ節約することで、先行するすべてのレイヤーを冗長に試すことができます。

于 2010-02-13T18:26:39.323 に答える
1

このようなまともなサイズのグラフがある場合、Neo4j は間違いなく良い方法だと思います。BFS アルゴリズムが組み込まれているだけでなく、ディスク上にデータを永続化するため、起動時間が短縮されます。

highscalability.com でこれをチェックしてください: NEO4J - A GRAPH DATABASE THAT KICKS BUTTOX

私は Neo4j を使用しましたが、そのドキュメントは非常に優れており、開始するのにほんの数分しかかからない、いくつかの優れた開始例が提供されています。

彼らをチェックしてください - 10分ガイドで始めましょう

于 2010-02-13T21:32:31.130 に答える
0

Neo4j はデータをグラフとしてデータベースに保存し、永続化し、Graph Traversal Api (BFS 、DBS 、A* Dijkstra ... )、または Cypher クエリ言語を使用してアクセスできます。

于 2014-04-17T15:56:41.167 に答える