メモ : 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など話題の生起が頻繁（数日レベルのものから数時間レベルのものまで）なものが対象だろうか。
対象（頂点）は、ユーザレベルか、投稿レベルか。
辺は？