13

非常に大きな無向で重みのないグラフ (数億の頂点から始まり、頂点あたり最大 10 個のエッジ) があり、分散されておらず、シングル スレッドのみで処理され、幅優先検索を実行したいとします。それらは I/O バウンドであると予想されるため、BFS に適したディスク ページ レイアウトが必要です。ディスク容量は問題ではありません。検索は、すべての頂点で同じ確率で開始できます。直観的には、異なるディスク ページ上の頂点間のエッジの数を最小限に抑えることを意味します。これは、グラフの分割の問題です。

グラフ自体はスパゲッティのように見えます。ランダムに相互接続されたポイントのランダムなセットを考えてみてください。短いエッジに偏りがあります。

問題は、どのようにして 1 つのパーティション グラフをこのように大きくするかということです。私が見つけた利用可能なグラフ パーティショナーは、メモリにのみ収まるグラフで動作します。ストリーミング グラフ パーティショニング アルゴリズムの説明も実装も見つかりませんでした。

または、BFS で適切に機能するディスク レイアウトを取得するためのパーティション グラフの代わりになるものがあるでしょうか?

現在、近似として、頂点に空間座標が関連付けられているという事実を使用し、頂点をヒルベルトのソート順でディスクに配置します。このようにして、空間的に近い頂点は同じページに配置されますが、それらの間のエッジの有無は完全に無視されます。私はもっ​​とうまくやれるだろうか？

別の方法として、頂点のヒルベルト ソート順を使用してグラフを断片に分割し、サブグラフを分割し、それらをつなぎ合わせて、継ぎ目の不十分な分割を受け入れることができます。

私がすでに調べたいくつかのこと：

  1. 数十億のノードと頂点を持つ大規模な重み付けされていない有向グラフを保存する方法
  2. http://neo4j.org/ - ディスク上でグラフ レイアウトを行う方法に関する情報が見つかりませんでした

パーティショニングの実装 (私が間違っていない限り、それらはすべてグラフをメモリに収める必要があります):

  1. http://glaros.dtc.umn.edu/gkhome/views/metis
  2. http://www.sandia.gov/~bahendr/chaco.html
  3. http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/
  4. http://www.cerfacs.fr/algor/Softs/MESHPART/

編集: グラフがどのように見えるか、および BFS はどこからでも開始できるという情報。編集:サブグラフの分割に関するアイデア

4

2 に答える 2

3

本当に「メモリに収まる」必要があるアルゴリズムはありません。必要に応じていつでもページインおよびページアウトできます。しかし、計算に不当に時間がかかることは避けたいと思います。また、一般的なケースでのグローバル グラフ パーティショニングは NP 完全問題であり、メモリに収まらないほとんどの問題では「不当に長く」なります。

幸いなことに、幅優先検索を実行する必要があります。つまり、幅優先検索が簡単な計算である形式が必要です。これを実行するアルゴリズムを私は知りませんが、少し余分なディスク領域を許可する場合は、独自の幅優先レイアウトを構築できます。

エッジが局所的な相互作用に偏っていない場合、グラフのもつれを解くことは困難になります。ローカルなやり取りに偏っている場合は、次のようなアルゴリズムをお勧めします。

  • データセット全体から頂点のランダムなセットを開始点として選択します。
  • 頂点ごとに、隣接するすべての頂点を収集します (データ セットを 1 回スイープします)。
  • 隣接する頂点のセットごとに、隣接する頂点のセットを収集し、それらに接続するエッジの数に従ってそれらをランク付けします。それらをすべて格納するスペースがページにない場合は、最も接続されている頂点を保持します。それらをすべて保存するスペースがある場合は、最も役に立たないものを破棄することをお勧めします (たとえば、ページ内に保持されるエッジの割合/ストレージを必要とする頂点の割合が「低すぎる」場合、「低すぎる」場合)。検索に実際にどれだけの幅が必要か、および剪定などができるかどうかによって異なります。その場合は、近隣にそれらを含めないでください。
  • 近隣がいっぱいになるまで、近隣を収集してランク付けするプロセスを繰り返します (たとえば、自分に合ったページ サイズがいっぱいになるまで)。次に、ランダムに選択された開始点の繰り返しを確認します。両方に表示される頂点の数が少ない場合は、どちらか一方からそれらを削除します。両方に多数の頂点が表示されている場合は、近隣を最高の (近隣の頂点/壊れたエッジの頂点) 比率に保ち、もう一方を破棄します。

これで、幅優先探索が内部に入る傾向があるという点で、ほぼ局所的に最適ないくつかの局所近傍ができました。幅優先探索が非生産的な分岐を非常に効果的に排除する場合、おそらくこれで十分です。そうでない場合は、おそらく隣接する近隣をクラスター化する必要があります。

隣接する近傍をあまりクラスター化する必要がない場合は、近傍にグループ化した頂点を脇に置き、すべての頂点が考慮されるまで残りのデータに対してプロセスを繰り返します。各頂点識別子を (vertex,neighborhood) に変更すると、完了です。エッジをたどると、どのページを取得するかが正確にわかり、それらのほとんどは構造を考慮して閉じられます。

隣接する近隣が必要な場合は、成長する近隣を追跡する必要があります。前のプロセス (無作為に選択し、近傍を成長させる) を繰り返しますが、近傍内で満たすエッジの数と、近傍を離れたエッジのうち既存のグループに含まれる割合の両方によって、近傍をランク付けします。重み係数が必要かもしれませんが、次のようなものです

score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside)

おそらくうまくいくでしょう。

現在、これは全体的にも局所的にも最適ではありませんが、これまたはそれに非常によく似たものは、局所的にうまく接続された構造を提供し、比較的高い相互接続性を持つ近隣のカバーセットを生成できるようにする必要があります.

繰り返しますが、幅優先検索で枝が枝刈りされるかどうかによって異なります。その場合、安価にできることは、ローカル相互接続を最大化することです。そうでない場合は、外部接続を最小限に抑える必要があります。その場合は、幅優先のセットをある程度のサイズまで収集し、それらを保存することをお勧めします (セットの端に重複があります)。ハード ドライブの容量によってひどく制限されているわけではありませんね)。

于 2010-01-29T17:14:26.923 に答える
2

あなたはHDF5を見たいかもしれません。HはHierarchicalの略ですが、グラフを保存したり、「グループ」というキーワードでドキュメントを確認したりできます。また、非常に大きなデータセット用に設計されています。私が正しく理解していれば、HDF5の「ファイル」は複数のo/sの「ファイル」に分散する可能性があります。現在、HDF5は単なるデータ構造であり、データ構造を低レベルおよび高レベルで操作するためのライブラリのセットです。頭から離れて、グラフ分割アルゴリズムのストリーミングについての手がかりはありませんが、データ構造を取得すると、正しいアルゴリズムの実装が容易になるという考えに固執しています。

メガグラフについて、あなたはすでに何を知っていますか？それ自体がまばらに接続されている密なサブグラフに自然に分割されますか？グラフのトポロジカルソートは、既存の空間ソートよりもディスク上のストレージのより良い基礎になるでしょうか？

そのような質問に対する明確な答えに失敗した場合、おそらくあなたは弾丸を噛み、グラフを複数回読んでパーティションを構築する必要があります。その場合、管理できる最速のI / Oが必要であり、ノード上のパーティションの洗練されたレイアウトは素晴らしいですしかし、それほど重要ではありません。グラフを他のサブグラフに対して単一のエッジを持つサブグラフに分割できる場合は、問題をより扱いやすくすることができます。

BFSに適したレイアウトが必要ですが、BFSは通常ツリーに適用されます。グラフには、すべてのBFSを開始するための一意のルートがありますか？そうでない場合、ある頂点からのBFSのレイアウトは、別の頂点からのBFSに対して最適ではありません。

于 2010-01-28T11:49:44.637 に答える