n-memo: 11月 2010

2010年11月29日月曜日

個別ミーティング 2010.11.29 Mon.

StreamGraph
・PEGASUSの動作モデルの理解（実行を通じて）⇒pptにまとめる
・Spade上でMapReduce的な反復処理の実装（案）
⇒これだけだとあまりストリーム的な要素がない
・ストリーム的な要素のアイデアを考える

ストリーム的な要素で簡単なものとしては、反復計算の途中に割り込んで
トポロジーの変化をする(頂点、辺の追加、削除）などが考えられる

2010年11月24日水曜日

大規模グラフ処理におけるデータ分散手法
・各タスクが必要とするデータは、どのノードが保持しているか
・（ローカルデータだけで処理できるのか）
・バッチ処理、データストリーム処理を問わず
・既存手法
・・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タスク、データ）を理解する必要がありそう？

2010年11月15日月曜日

メモ : Efficient PageRank on GPU Clusters

http://www.ipsj.or.jp/09sig/kaikoku/2010/ARC184HPC128.html
===
（22）Efficient PageRank on GPU Clusters
　　　○Cevahir Ali（東工大），Aykanat Cevdet，Turk Ata（Bilkent大），
　　　Cambazoglu B. Barla（Yahoo! Research），Nukada Akira，Matsuoka Satoshi（東工大）
===
GPGPUを使ったグラフ処理の研究自体は当然既にある

PEGASUSの各アルゴリズム

Degree, PageRank, RWR など各種アルゴリズムがデフォルトで実装されている
デモの実行方法やスクリプトの場所などはマニュアルpdfを参照

例 : Degree
実行スクリプト : run_dd.sh
デモスクリプト : do_dd_catstar.sh
Javaプログラム : src/pegasus/degdist/DegDist.java

マニュアルpdfにはアルゴリズムの実装の詳細などは載っていないので、詳しく知りたければ元論文を読むなりすること

---

グラフの記述方法
頂点は番号(o-origin)で識別される
（Pregelのように文字列形式の識別子を持つわけではない）
辺は、ソース頂点番号、デスト頂点番号の対で表す

具体例を見ればわかると思う(catepillar_star.edge)

---

PEGASUSは、Hadoopを利用したグラフアルゴリズム処理システム。
MapReduce計算モデル上でグラフアルゴリズムを処理する。
アルゴリズムの「いくつかは」、GIM-Vというモデルに基づいて実行される。
（すべてのアルゴリズムがGIM-Vを用いているわけではない）

……GIM-Vを利用しているのはアルゴリズム実装であって、PEGASUSのフレームワークレベルが利用しているわけではない