2011年9月14日水曜日

殴り書き

SSSPのような反復回数が多くなる(3桁以上)アルゴリズムには向かない

2011年8月3日水曜日

ぱーてぃしょにんぐ、しらべもの

Spectral Clusteringについて

Data Similarity Graphというグラフを定義し、そのグラフを対象とした話。
密行列なのでBSPやGIM-Vに向かない?
他のGraph Partitioningアルゴリズムを考えるべきかも。

勘違いしてるかも。

参考文献、URL
・d.hatena.ne.jp/mamoruk/20090128/p1
・Qianjun Xu, Marie desJardins and Kiri L. Wagstaff. Active Constrained Clustering by Examining Spectral Eigenvectors. Proc of Discovery Science 2005.
・・(2章)

今後

調べるアルゴリズム(アプリケーション)
・最短経路問題
・中心性解析 (Between Centrality)
・Random Walk with Restart
・Spectral Clustering (Graph Partitioning)

モデルとして、GIM-Vでなければならなかった理由?
・特になし。しいて言えば、PEGASUSがオープンソースだったから。
・Pregel,BagelなどのBSPでもいいと思う。実装コストはともかく

2011年5月16日月曜日

個別ミーティング

TODO in short term:
GIM-V on System S と PEGASUS の性能比較

TODO in long term:
Incremental Algorithm の調査、Stream化

2011年4月27日水曜日

2011.04.27(Wed.) 全体ミーティング メモ(+α)

今後の全体ミーティング

1回につき2人、1人あたり30分

良い論文を書くために

客観的な定量的評価、定性的評価
  • マイクロベンチマーク
  • 実アプリケーションによる評価
  • マジックナンバーは3 (3種類のアプリケーションで評価)
  • プロファイリングも重要 (oprofile, vmstat, ...)
論文はわかりやすく (異分野の人が読んでもわかるように)
  • SACSISに採択された論文の書き方を参考に
ベースとなる手法自体はシンプルでも、十分な評価が行われていれば良い研究となる。

SACSIS 2011

1人2本、聴講してまとめて後で発表する。
(題目が他の人と被らないように、要相談)

Activity

  • 大規模グラフストリーム処理(ganse, ueno)
  • インクリメンタルグラフ処理(ganse,nishii)
  • APU ストリームコンピューティング(matsuura)
  • StreamScale/ElasticStream(miyuru,ueno,takeno,ishii)
  • Automatic Optimization(miyuru)
  • Graph500(watanabe,ueno)
  • GPU グラフ処理(shirahata, ueno)
(グエンさんについての確認を忘れた)

助言教員

GWの予定


その他

投稿する論文の校正を、提出1日前などぎりぎりになってから出さないように。早めにすること。

全体ミーティング以外のメモ

データストリーム処理に向いたグラフアプリケーション
  • k-means (クラスタリング)
  • PageRank
  • 最短路問題
リアルタイム処理の分類
  • ハードRT
  • ファームRT
  • ソフトRT
CDR

2011年4月25日月曜日

IGIMV (DE版) バグ?

snk_managerに謎の出力が入る.バイナリファイル扱いされる.
stop_stream せずに連続して submit_stream cancel_stream を繰り返していると生じる?
igimv の方ではなく,gimv の方で生じている?

see:
/nfs/home/nishii/streamgraph/igimv/proto3/gimv/data/result_de_e-5/result-050-3
/nfs/home/nishii/streamgraph/igimv/proto3/gimv/data/result_de_e-5/result-050-4
など

2011年4月11日月曜日

StreamGraph(Incremental GIM-V) 現状と今後の方向性

Incremental GIM-V(以下、IGIMV)の現状としては、一応SPADE+UDOPで実装したものがあるが、これには以前の記事(Incremental GIM-V デバッグ中)に記したとおり、オペレータ(プロセス?)のタプルバッファによりデッドロックに似た現象が生じ、ある程度以上の数の辺を含むグラフを正常に処理できないという問題がある。
これを解決するために、作業オペレータを二種類に分割するよう実装する予定である。

実装から離れて、IGIMVの研究的な意味での貢献を考えてみる必要もある。現状では、Incremental PageRank(以下、IPR)の手法をPEGASUSのグラフ計算モデル(GIM-V)に当てはめようとはしているが、これが本当に効果的であるかは自明でない。PageRankへの有用性は、当然IPRの論文で触れられているが、それ以外についてはどうなるのか。
このあたりをはっきりとしないと、研究としての貢献が主張できない。

あまり計算モデルの一般化ということを考えずに、PageRank「など」のグラフ構造解析をストリーム的に効率的に行う、という方向で研究を進めるのはどうか、と考えている。

まず、元々のIPRは、データストリーム処理のための手法ではなく、バッチ処理を効率的に行うためのものであり、IPRはActual PageRank(全体を解析する手法)と同様の、「正しい」解析結果を得られる手法である。
ストリーム的には、このIPRのように完全な解析を行うのではなく、計算の範囲を構造変化から近い頂点(距離2,3程度?適切な距離はその頂点のページランクにも依存?)に限定して行い、完全な解析はバッチ処理(IPR)に任せる、などというのはどうだろうか。

ストリーム的に行うために、オンメモリ性を考える必要もある。頂点や辺のデータはファイルシステム上に保存しておき、計算に必要のないデータはメモリにロードしないようにする。

======

いずれにせよ、FIT(4/21〆切)までに貢献のある論文の形まで持っていくことは難しいような気がする……。
頑張って書こう!
Incremental GIM-V は、グラフ処理としても制限がきつく、データストリーム処理としてもまだ高速化(簡略化)の余地のある手法だけど、プロトタイプとしての提案である、という方向性で書く。