GIM-V PageRankへのIncremental PageRankの応用を考える。
3節のStep3までは同じようにやればよい。
Step4を実行することを考える。
Vbに含まれる頂点のPageRankはこの時点で定まっていて、変更の必要はない。
VQ : 構造変化が生じた頂点、およびそこからたどれる頂点の集合
VQと、VQ内を結ぶ辺(EQ)からなるグラフ(GQ)に対してGIM-V PageRank(+拡張)を実行する。(論文中のEQ,GQの定義とは異なる点に注意)
GIM-V PageRankの手法では、ページ遷移を表わす重みをcombine2()で計算、その重みの合計からPageRankの計算をcombineAll()で行う。
combine2()は、GQ内の値からしか計算されない。しかし、VQ内の頂点のPageRankの計算はcombine2()の結果だけでなく、Vbからの重みも加味して行う必要がある。そこで、GIM-V PageRankに拡張を施す。すなわち、combine2()の結果に加えて、Vbからの重みもcombineAll()の計算対象にするように拡張すればよい。
======
Incremental PageRankの手法をGIM-V PageRankに応用する手法はわかったが、GIM-V一般には応用できるだろうか。GIM-Vによる他のアルゴリズムをまだちゃんと理解していないので、それも調べる必要がある。RWRには適用できそう。
Incremental PageRankの手法は、PageRankの計算構造に着目した最適化によるものなので、グラフ処理一般にそのまま応用できるだろうか。
======
Incremental PageRank
グラフ構造が変化(※1)したときに、
・PageRankが変化せず(※2)、他の頂点にも影響を及ぼさない頂点
・PageRankは変化しないが、他の頂点のPageRankの計算に必要な頂点
・PageRankが変化する点(構造が変化した点、変化の影響を受ける点)
に分けて計算を行う。
(※1)グラフ構造の変化として、PageRankの場合、(頂点追加、頂点削除、辺追加、辺削除)の4通りが考えられる。辺の追加と削除の場合、その辺で繋がる頂点の2つともを「構造が変化した点」として扱う。(はず。論文中では明記されていない…と思う。)
(※2)実際には、頂点数の変化に伴いPageRankの値に係数をかけるという、簡単な再計算を行う必要はある。
2011年1月7日金曜日
2010年12月28日火曜日
スケジュール管理(研究的な意味ではなく)
自分がいつ授業があるか、いつの就職説明会に興味があるか、いつレポート締め切りに追われているか、いつ試験があるか、いつ東京を離れているか、etcetc...、などの情報は逐次カレンダーに追加しています
http://www.google.com/calendar/embed?src=fpmuacke.2c%40gmail.com&ctz=Asia/Tokyo
万が一、私のカレンダーの閲覧権限を持っていないという方がいらっしゃいましたら、ご連絡ください
2010年12月22日水曜日
StreamGraph 研究の方向性とか
グラフ関連の研究ということで、2つのビジョンがある。
後者の方を見ると
インクリメンタルグラフ処理システムの研究を行うために
まとめ:やりたいこと
- 既存のバッチ型グラフ処理システム(ex. PEGASUS(GIM-V))のGPU高速化
- Framework for incremental graph processing
- PageRank, RWRなどのGPU実装に関する研究は既にある
- GIM-Vはそんなに汎用的な計算モデルでもない
- ⇒GIM-VをGPU実装しても、既存研究に対してあまり差別化できない?
後者の方を見ると
- incrementalなPageRank計算アルゴリズムが存在
- ⇒各マイニングアプリケーションに特有のインクリメンタルな計算モデルはある
- 汎用的なインクリメンタルなグラフ処理の計算モデルを提唱したい
インクリメンタルグラフ処理システムの研究を行うために
- インクリメンタルGIM-V (or other) を実装
- その上でPageRankアルゴリズムを実装
- バッチ処理とのgapを調べる
まとめ:やりたいこと
- インクリメンタルなグラフ処理の計算モデルの提唱
- incrementalなPageRank計算アルゴリズムについて理解
- incremental GIM-V (or other) on System S (or Hadoop, or StreamScale) の実装
2010年12月8日水曜日
メモ
並列分散環境下におけるデータストリームグラフ処理に対して、ネットワークインテンシブなアプリケーションのための、ネットワークコストを削減するデータ(タスク)配置手法を考える
……その前に、
・バッチグラフ処理での配置手法に関する研究を調べる
・バッチ処理一般(MapReduceなど)における配置手法に関する研究を調べる
===================================
そもそも研究がどういう方向性に行くのかまだ決まっていない……アイディアがどこからともなくふってくるわけでもないので、いろいろ調べてみるしかないのかも
……その前に、
・バッチグラフ処理での配置手法に関する研究を調べる
・バッチ処理一般(MapReduceなど)における配置手法に関する研究を調べる
===================================
そもそも研究がどういう方向性に行くのかまだ決まっていない……アイディアがどこからともなくふってくるわけでもないので、いろいろ調べてみるしかないのかも
2010年11月29日月曜日
個別ミーティング 2010.11.29 Mon.
StreamGraph
・PEGASUSの動作モデルの理解(実行を通じて)⇒pptにまとめる
・Spade上でMapReduce的な反復処理の実装(案)
⇒これだけだとあまりストリーム的な要素がない
・ストリーム的な要素のアイデアを考える
ストリーム的な要素で簡単なものとしては、反復計算の途中に割り込んで
トポロジーの変化をする(頂点、辺の追加、削除)などが考えられる
・PEGASUSの動作モデルの理解(実行を通じて)⇒pptにまとめる
・Spade上でMapReduce的な反復処理の実装(案)
⇒これだけだとあまりストリーム的な要素がない
・ストリーム的な要素のアイデアを考える
ストリーム的な要素で簡単なものとしては、反復計算の途中に割り込んで
トポロジーの変化をする(頂点、辺の追加、削除)などが考えられる
2010年11月24日水曜日
メモ : StreamGraph 思考メモ
大規模グラフ処理におけるデータ分散手法
・各タスクが必要とするデータは、どのノードが保持しているか
・(ローカルデータだけで処理できるのか)
・バッチ処理、データストリーム処理を問わず
・既存手法
・・Pregel →
・・・各タスクの分散 : Hash(id) mod N
・・・メッセージパッシング、ローカルデータのみ
・・PEGASUS →
・・・Mapタスク、Reduceタスクの分散はHadoop依存
・・・データはOutput関数で渡し、Map、Reduce関数の引数で受け取る
・・・各タスクが必要とするデータはローカルデータのみ(HDFSは使わない)
GIM-V の SystemS 上実装
・研究の方針としては、数多くあるグラフアルゴリズムに対する汎用性はそんなに考えなくてよい?
・(GIM-V のように特定のアルゴリズムだけ解ければよい?)
・GIM-V のナイーブ実装、高速実装をまず理解する必要がある
・SystemS の UDOP のフィードバックループで実装できる?
・オリジナルの GIM-V は(多分)ユーザ操作による辺、頂点の追加、削除を考慮していない?(そういう機能を持たない)
GIM-V BASE implementation (IV. A)
・行列のうち値を指定していない(空)箇所はcombine2の計算がされない
・→疎行列でもそれなりに効率が良い(多分)
==============================
GIM-V拡張で辺の追加、削除を実装するのは、行列Mの値を更新すればいいだけなので多分簡単。問題は頂点の追加、削除で、行列M、ベクトルVの大きさが変化することになるので困難。
==============================
(2010.11.30 Tue.)
GIM-Vの反復の終了
PageRankを例にする。(src\pegasus\pagerank\PagerankNaive.java)
反復処理を行っているのが383~404行。
終了条件は、
1. ベクトルの値の変化がなくなったとき
2. 規定回数反復を行ったとき
1については、PageRankの値がスレッショルド(converge_threshold==0.000001)以上の変化が生じなくなった時を指す。(186~190行)
2については、デフォルトの規定回数は32回(niteration==32)となっている。
==============================
(2010.12.01 Wed.)
バッチ処理におけるデータ量爆発と、データストリーム処理におけるそれとの違いが判らない……
==============================
(2010.12.03 Fri.)
ストリーム処理向けグラフ処理のアプリケーション
http://suzumura-lab.blogspot.com/2010/11/streamgraph.html
膨大(かつstatic)なWebグラフに対するPageRankの計算を計算しているところで最も有名なのはGoogleだと思うが、そのGoogleでもPageRankの更新を行うのは2~4ヶ月に一度程度。こういった用途であればバッチ処理的に行うのが適切だろう。
ストリーム的なPageRankの計算となると、ミニブログやブログ、SNSなど話題の生起が頻繁(数日レベルのものから数時間レベルのものまで)なものが対象だろうか。
対象(頂点)は、ユーザレベルか、投稿レベルか。
辺は?
・各タスクが必要とするデータは、どのノードが保持しているか
・(ローカルデータだけで処理できるのか)
・バッチ処理、データストリーム処理を問わず
・既存手法
・・Pregel →
・・・各タスクの分散 : Hash(id) mod N
・・・メッセージパッシング、ローカルデータのみ
・・PEGASUS →
・・・Mapタスク、Reduceタスクの分散はHadoop依存
・・・データはOutput関数で渡し、Map、Reduce関数の引数で受け取る
・・・各タスクが必要とするデータはローカルデータのみ(HDFSは使わない)
GIM-V の SystemS 上実装
・研究の方針としては、数多くあるグラフアルゴリズムに対する汎用性はそんなに考えなくてよい?
・(GIM-V のように特定のアルゴリズムだけ解ければよい?)
・GIM-V のナイーブ実装、高速実装をまず理解する必要がある
・SystemS の UDOP のフィードバックループで実装できる?
・オリジナルの GIM-V は(多分)ユーザ操作による辺、頂点の追加、削除を考慮していない?(そういう機能を持たない)
GIM-V BASE implementation (IV. A)
・行列のうち値を指定していない(空)箇所はcombine2の計算がされない
・→疎行列でもそれなりに効率が良い(多分)
==============================
GIM-V拡張で辺の追加、削除を実装するのは、行列Mの値を更新すればいいだけなので多分簡単。問題は頂点の追加、削除で、行列M、ベクトルVの大きさが変化することになるので困難。
==============================
(2010.11.30 Tue.)
GIM-Vの反復の終了
PageRankを例にする。(src\pegasus\pagerank\PagerankNaive.java)
反復処理を行っているのが383~404行。
終了条件は、
1. ベクトルの値の変化がなくなったとき
2. 規定回数反復を行ったとき
1については、PageRankの値がスレッショルド(converge_threshold==0.000001)以上の変化が生じなくなった時を指す。(186~190行)
2については、デフォルトの規定回数は32回(niteration==32)となっている。
==============================
(2010.12.01 Wed.)
バッチ処理におけるデータ量爆発と、データストリーム処理におけるそれとの違いが判らない……
==============================
(2010.12.03 Fri.)
ストリーム処理向けグラフ処理のアプリケーション
http://suzumura-lab.blogspot.com/2010/11/streamgraph.html
膨大(かつstatic)なWebグラフに対するPageRankの計算を計算しているところで最も有名なのはGoogleだと思うが、そのGoogleでもPageRankの更新を行うのは2~4ヶ月に一度程度。こういった用途であればバッチ処理的に行うのが適切だろう。
ストリーム的なPageRankの計算となると、ミニブログやブログ、SNSなど話題の生起が頻繁(数日レベルのものから数時間レベルのものまで)なものが対象だろうか。
対象(頂点)は、ユーザレベルか、投稿レベルか。
辺は?
2010年11月17日水曜日
TODO list 20101117 Wed. (StreamGraph)
- PEGASUS, Pregel の動作原理を理解
- それぞれの計算モデルの応用性を把握(何に向いているか、いないか)
- ストリーム処理に向いているか否か考察
- System SなどDSMS上で実装するにはどうすればいいか考察
GIM-V(PEGASUS)計算モデルの高速実装は論文をちゃんと読んでちゃんと実装しないといけないので、時間がかかるかも
ナイーブ実装ならばそんなに難しくない?
===
PEGASUSの分散手法を理解する前に、MapReduce(Hadoop)の分散手法(Mapタスク、Reduceタスク、データ)を理解する必要がありそう?
登録:
投稿 (Atom)