10

PageRankが固有値の形式であり、それがMapReduceが導入された理由であるために可能です。しかし、実際の実装には問題があるようです。たとえば、すべてのスレーブコンピューターがマトリックスのコピーを維持する必要がありますか？

4

5 に答える 5

9

PageRank は、ネットワークの定常状態の離散フロー条件を繰り返し見つけることにより、支配的な固有ベクトルの問題を解決します。

NxM 行列 A がノード n からノード m へのリンクの重み (フローの量) を表す場合、

p_{n+1} = A . p_{n}

p が定常状態 (p_n+1 = p_n) に収束した極限では、これは固有値 1 の固有ベクトル問題です。

PageRank アルゴリズムでは、行列をメモリに保持する必要はありませんが、密度の高い (疎でない) 行列では効率が悪くなります。密な行列の場合、MapReduce は間違ったソリューションです。ノード間の局所性と広範な交換が必要です。代わりに、LaPACK と MPI およびその仲間を検討する必要があります。

wukong ライブラリ(ruby の Hadoop ストリーミング) またはHeretrix pagerank サブモジュールで動作する pagerank 実装を確認できます。(Heretrix コードは Heretrix とは独立して実行されます)

(免責事項: 私は wukong の著者です。)

于 2009-04-21T19:30:47.663 に答える
6

前文:

データを適切に隔離すれば、すべてのマシンに完全なデータセットがなくても、並列計算の結果を得ることができます。

たとえば、次のループを見てください。

for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        m[i][j]++; 
    }
}

そして、次のレイアウトのマトリックスが与えられます。

       j=0   j=1   j=2
 i=0  [   ] [   ] [   ]
 i=1  [   ] [   ] [   ]
 i=2  [   ] [   ] [   ]

J 列を各コンピューターに送信し、単一の列を並列で計算できるように、並列構造が存在します。並列化の難しい部分は、依存関係を含むループがある場合です。

for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        //For obvious reasons, matrix index verification code removed
        m[i][j] = m[i/2][j] + m[i][j+7]; 
    }
}

明らかに、上記のようなループは非常に問題になります (行列インデクサーに注意してください)。しかし、これらのタイプのループを展開し、効果的な並列アルゴリズムを作成するための手法は存在します。

答え:

Google が、すべてのスレーブ コンピューターで行列のコピーを維持することなく固有値を計算するソリューションを開発した可能性があります。-または- 彼らは、モンテカルロやその他の近似アルゴリズムなどを使用して、「十分に近い」計算を開発しました。

実際、Google は PageRank アルゴリズムに必要な計算をできる限り効率的にするために、できる限りの努力をしていると言っても過言ではありません。これらのようなマシンを実行している場合(イーサネット ケーブルに注意してください)、大きなデータセット (数百ギガ) を転送することはできません。これは、コモディティ NIC カードのハードウェア制限を考えると不可能だからです。

そうは言っても、Google はプログラマー コミュニティを驚かせるのが得意であり、その実装はまったく異なるものになる可能性があります。

ポストタンブル:

並列計算に適したリソースには、OpenMPやMPIなどがあります。どちらの並列実装も、非常に異なるパラダイムから並列コンピューティングにアプローチしており、その一部はマシン実装 (クラスター対分散コンピューティング) に由来します。

于 2008-12-24T00:02:06.883 に答える
1

特殊な構造を持つもの（たとえば、スパース行列や特定のブロックパターンを持つもの）を除いて、ほとんどの行列では扱いにくいと思います。行列係数と固有値の間の結合が多すぎる方法があります。

PageRankは、特殊な形式の非常にスパースな行列を使用し、その固有値の計算から得られる結論は、ほぼ確実に一般的な行列には適用されません。（編集：これは面白そうな別のリファレンスです）

于 2008-12-24T00:47:47.040 に答える
1

Apache hamaプロジェクトには、Jacobi 固有値アルゴリズムの興味深い実装があります。Hadoop で動作します。マップの縮小ではなく、マトリックスのスキャンで回転が発生することに注意してください。

于 2010-02-08T23:53:46.343 に答える
1

私は今自分自身に答えることができます。PageRank アルゴリズムは、いくつかの自己乗算で固有値に収束する疎行列を利用します。したがって、PageRank の実践では、Map/Reduce 手順が有効です。Map プロシージャで行列乗算を実行し、Reduce プロシージャで疎行列を形成できます。しかし、一般的な行列の固有値を見つけるには、依然としてトリッキーな問題です。

于 2009-01-01T14:28:21.557 に答える