2010年12月28日火曜日

スケジュール管理(研究的な意味ではなく)

自分がいつ授業があるか、いつの就職説明会に興味があるか、いつレポート締め切りに追われているか、いつ試験があるか、いつ東京を離れているか、etcetc...、などの情報は逐次カレンダーに追加しています

http://www.google.com/calendar/embed?src=fpmuacke.2c%40gmail.com&ctz=Asia/Tokyo

万が一、私のカレンダーの閲覧権限を持っていないという方がいらっしゃいましたら、ご連絡ください

2010年12月22日水曜日

StreamGraph 研究の方向性とか

グラフ関連の研究ということで、2つのビジョンがある。
  1. 既存のバッチ型グラフ処理システム(ex. PEGASUS(GIM-V))のGPU高速化
  2. 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など)における配置手法に関する研究を調べる

===================================
そもそも研究がどういう方向性に行くのかまだ決まっていない……アイディアがどこからともなくふってくるわけでもないので、いろいろ調べてみるしかないのかも

2010年11月29日月曜日

個別ミーティング 2010.11.29 Mon.

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

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を使ったグラフ処理の研究自体は当然既にある