外部メモリグラフの走査

無向グラフの場合${\displaystyle G}$ムナガラとラナデ^{[ 2 ]}は、 以下の外部メモリアルゴリズムを提案した。

させて${\displaystyle L(t)}$幅優先探索レベル t のノードを表し、${\displaystyle A(t):=N(L(t-1))}$レベル t-1 の近傍の多重集合とする。すべての t について、${\displaystyle L(t)}$から構築できます${\displaystyle A(t)}$それを集合に変換し、以前に訪れたノードを除外することによって。

1. 作成する${\displaystyle A(t)}$すべての頂点の隣接リストにアクセスすることによって${\displaystyle L(t-1)}$このステップには${\displaystyle O(|L(t-1)|+|A(t)|/(D\cdot B))}$入出力。
2. 次${\displaystyle A'(t)}$から作成されます${\displaystyle A(t)}$重複を削除することによって。これは、ソートによって実現できます。${\displaystyle A(t)}$続いて、スキャンと圧縮の段階が必要${\displaystyle O(\operatorname {sort} (|A|))}$入出力。
3. ${\displaystyle L(t):=A'(t)\backslash \{L(t-1)\cup L(t-2)\}}$は、並列スキャンによって計算されます。${\displaystyle L(t-1)}$そして${\displaystyle L(t-2)}$そして必要とする${\displaystyle O((|A(t)|+|L(t-1)|+|L(t-2)|)/(D\cdot B))}$入出力。

このアルゴリズムの入出力の総数は、以下の点を考慮すると次のようになる。${\displaystyle \sum _{t}|A(t)|=O(m)}$そして${\displaystyle \sum _{t}|L(t)|=O(n)}$そしてそれは${\displaystyle O(n+\operatorname {sort} (n+m))}$。

L ( t )を計算するために必要な、説明した3つのステップを視覚化した図が右の図に示されています。

MehlhornとMeyer ^{[ 3 ]}は、MunagalaとRanade（MR）のアルゴリズムに基づいて、その結果を改善するアルゴリズムを提案した。

これは2つのフェーズから構成されます。第1フェーズではグラフの前処理を行い、第2フェーズでは第1フェーズで収集した情報を用いて幅優先探索を実行します。

前処理段階では、グラフは互いに素な部分グラフに分割されます。${\displaystyle S_{i},\,0\leq i\leq K}$小径で、さらに外部ファイルを構築することで隣接リストを適切に分割します。${\displaystyle F=F_{0}F_{1}\dots F_{K-1}}$、 どこ${\displaystyle F_{i}}$すべてのノードの隣接リストが含まれています${\displaystyle S_{i}}$。

幅優先探索フェーズはMRアルゴリズムと同様です。さらに、このアルゴリズムはソートされた外部ファイルHを保持します。このファイルは次のように初期化されます。${\displaystyle F_{0}}$さらに、作成された幅優先探索レベルのノードには、ファイルの識別子が含まれています。${\displaystyle F_{i}}$それぞれのサブグラフの${\displaystyle S_{i}}$ランダムアクセスを使用して構築する代わりに${\displaystyle L(t)}$ファイルHが使用されます。

1. ソート済みリストの並列スキャンを実行する${\displaystyle L(t-1)}$そしてH。ノードの隣接リストを抽出する。${\displaystyle v\in L(t-1)}$それはHで見つけることができます。
2. Hで見つからなかった残りのノードの隣接リストを取得する必要があります。${\displaystyle L(t-1)}$パーティション識別子が返されます。ソートと重複の削除後、それぞれのファイル${\displaystyle F_{i}}$一時ファイルF'に連結できます。
3. 欠落している隣接リストは、スキャンによってF'から抽出できます。次に、残りの隣接リストを1回の処理でHにマージします。
4. ${\displaystyle A(t)}$は単純なスキャンによって作成されます。パーティション情報は、各ノードに添付されます。${\displaystyle A(t)}$。
5. このアルゴリズムはMRアルゴリズムと同様の手順で進行する。

Hではエッジのスキャン頻度が高くなる可能性があるが、隣接リストを取得するための非構造化I/Oは削減される。

このアルゴリズムの入出力の総数は${\displaystyle O\left({\sqrt {\frac {n\cdot (n+m)}{D\cdot B}}}+\operatorname {sort} (n+m)\right)}$