Rescale で R を使用して PageRank をスケーリングする

ここ数年にわたるデータ駆動型アプリケーションの急増により、多くのアプリケーションが巨大なデータセットの高度な分析に依存するようになりました。 一方、MapReduce ベースのフレームワークは次のようになります。 Hadoopのは、アルゴリズムをビッグ データ セットに拡張することを容易にしますが、制限的なプログラミング フレームワークにより、既存の計算を MapReduce のモデルに適合させることが困難になります。
配列ベースの言語など Rは、統計分析を記述するためのより自然で表現力豊かなフレームワークを提供します。 1996 年に導入されて以来、R は世界中の統計学者やデータ サイエンティストに選ばれる言語の XNUMX つになりました。 このパッケージには、活発なコミュニティとインタラクティブなエコシステムが備わっていますが、重大な制限もあります。 R はシングルスレッドであり、より大きなデータセットではうまく拡張できません。 この欠点により、統計学者によって作成された効果的な統計パッケージが、自明でないデータセットに対しては役に立たなくなります。
アルゴリズムが非常にデータ集約的な場合は、Hadoop がより良いソリューションであることがわかります。 ただし、既存の R コードを賢くリファクタリングすると、R のパフォーマンスを向上させることができます。そうは言っても、私は R の MPI ラップアラウンドをテストすることにしました。 リンピ.

【数1】PR（A）=（1-d）+ d（PR（T1）/ C（T1）+ ... + PR（Tn）/ C

PR(A) – ノード A のページランク

d – 減衰係数

PR(Tn)/C(Tn) – PR(A) に寄与する Tn のスコアの一部。T1…Tn は A にリンクするノードです。

PageRank の最も単純なバージョンでは、最初はすべてのノードが同じランクを持ち、各ノードが収束するまで隣接するノードに等しいスコアを分配すると仮定します。 このアルゴリズムは、PageRank ベクトルに対する連続した更新の差が非常に小さな値よりも小さい場合に収束します。

並列化の戦略

この計算には XNUMX つの主要なデータ構造があります。 隣接行列はグラフを表し、PageRank ベクトルにはすべてのノードのスコアが含まれます。 各スレッドは隣接行列の行の一部でのみ機能しますが、各反復後に PageRank ベクトル全体がスレーブ スレッドで利用できるようにする必要があります。 これにより、更新された PageRank が次の反復で使用されることが保証されます。 MPI操作を使用しました 散乱 隣接行列をスレーブ スレッドに配布し、操作を実行します。 オールギャザーブ 使われた 各反復後に部分的な PageRank ベクトルの結果を収集します。

に関する実験 プラットフォーム

私が使用 スタンフォードネットワーク分析プロジェクト 私の実験用のデータセット、特に 高エネルギー物理引用ネットワーク データセット。 グラフには 34,546 個のノードと 421,578 個のエッジが含まれています。 バニラのシーケンシャル バージョンの実行時間は 653.89 秒でした。

実行時間グラフは、12 スレッド (86.733 秒) と 16 スレッド (68.38 秒) の間でランタイムの増加が徐々に減少する指数関数的な減衰分布に従います。

非常に大規模なデータセットに拡張することは依然として困難ですが、Rescale プラットフォームで実証されているように、Rmpi などのフレームワークを使用して、R を中程度のサイズのデータ​​セットに拡張することができます。
このシミュレーションを Rescale アカウントにインポートできます こちら。 Rescale アカウントをまだお持ちでない場合は、こちらにアクセスしてください。 www.rescale.com/signup 今すぐ無料アカウントにサインアップしてください。
Rescale について詳しくは、次のサイトをご覧ください。  。 エンジニアリングおよび科学シミュレーションに Rescale の使用を開始するには、お問い合わせください。 info@rescale.com.