2012年1月27日金曜日

ぐらふすぺくとる

なぜしゅーろんが終わった今になって今更ぐらふすぺくとるの理論について調べているのか
書籍まで読むのは無理そうだけど

とりあえずS先生の講義資料を入手したのでそれを読む

はてなダイアリーより
d.hatena.ne.jp/smly/20080817/1218988549

Yale大のDan Spielman氏による講義資料 : Spectral Graph Theory and its Applications

Fan R. K. Chung氏による書籍 : Spectral Graph Theory (Cbms Regional Conference Series in Mathematics)

Wikipedia : Spectral graph theory

2012年1月25日水曜日

スペクトラルクラスタリング、可視化


適当に1000頂点のツリーをランダムに作成、スペクトルを計算、Cytoscapeでスペクトルを基に色分けしてみた。

インクリメンタルグラフクラスタリング

インクリメンタルな更新をアニメーションで可視化してプレゼンテーションしたい

Cytoscape
graphviz -> 不適

2012年1月14日土曜日

fullsc2.cppに関して

UNICORNの実験で使われているクロネッカーグラフのSCALE*.txtを実験データに用いたところ、
処理が異常に早く終わり、λが0になってしまう。うまく動かない。
→次数が0の頂点が存在するため?
→or グラフが連結でないため?

対数正規分布グラフで実行したところ、正常に動いた。
必ず次数が1以上になるように生成している。
v=1000,e=37575(重複を除外)で、システムとの入出力時間も含めて
63.6秒かかった。

2011年11月27日日曜日

memo

LD_LIBRARY_PATH

2011年11月17日木曜日

ぐらふ

BFS前処理による計算範囲の限定 (original idea from Incremental PageRank)
→有向グラフ
→PageRank
収束判定に基づく計算範囲の限定 (original idea from Adaptive PageRank)
→有向グラフ、無向グラフ
→PageRank, RWR, SSSP

[new]名称未定 : Incremental Spectral Clustering のための通信
→無向グラフ
→I.SC

2011年11月4日金曜日

クラスタリングメモ、続き

*Parallel Incremental Graph Partitioning, Chao-Wei Ou and Sanjay Ranka, Member, IEEE
線形計画法(LP)によるインクリメンタルグラフパーティショニング
(古い論文 : Parallel Incremental Graph Partitioning Using Linear Programming)

===

実装・実験するもの
・Full SC (k=2)
・Incremental SC (k=2)
(・Incremental Partitioning with LP (k=2, 3, ...) : 実装間に合わないと思う)

実行時間、収束回数
分割結果の評価(頂点コスト、通信コストを評価する?)

(Incremental Partitioning with LPで、初期分割はどうするか?)

クロネッカーグラフ
頂点重み(1)と辺重み(1?)は固定

===

以下を並行して行っていく
・SC, Incremental SCの実装に関するppt作成、ラフに
→11月中旬、下旬まで
・実装
→12月上旬、中旬まで
・実験
→12月内に

===

他の参考文献・URL

glaros.dtc.umn.edu/gkhome/publications/gp
METISとか

www.sciencedirect.com/science/article/pii/S1574013707000020
Glaph Clustering, サーベイ論文

2011年10月19日水曜日

クラスタリングメモ

辺の追加・更新→類似度行列の拡大・更新
更新される要素 : w_{i,j} ( = w_{j,i} )
類似度行列を拡大するとき、要素の初期値は0

スペクトラルクラスタリングは必ずしもグラフを対象をしたクラスタリング手法ではないが、
全頂点対間の類似度を類似度行列として扱っているので、
類似度行列をグラフの隣接行列とみなせばグラフにも使える、ということかな?

他のグラフクラスタリング手法について調査

===

Incremental Spectral Clustering With Application to Monitoring of Evolving Blog Communities
関連研究よりメモ

[14]Ng et al. On spectral clustering: Analysis and an algorithm.
マルチウェイ(k=3クラスタ以上)のクラスタリング手法。
固有値の小さいものから順にk個固有ベクトルを取り出して(k次元の特徴量を抽出して)
n×k行列を作成。各行を頂点の値としてk-meansなどでクラスタリング。

Spectral Clustering以外のIncremental Methodsについて

[9]Gupta et al. A single pass generalized incremental algorithm for clustering.
ストリームは辺じゃなくて頂点、というかそもそもグラフが対象じゃない。
クラスタ中心と追加された頂点との比較ができないといけないので。
[8]k-medoids?頂点ストリームが対象?
[2]これも距離空間上の頂点ストリームが対象
[4][11]PageRankの話

===

遺伝的アルゴリズムを使ったグラフ分割

2011年10月4日火曜日

新しいigimvで

PageRankの再実装
Spectral Clusteringの実装
あと評価

現状、小さな密行列に対して疑似逆行列を計算する方法を考える必要がある

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 は、グラフ処理としても制限がきつく、データストリーム処理としてもまだ高速化(簡略化)の余地のある手法だけど、プロトタイプとしての提案である、という方向性で書く。

2011年4月8日金曜日

Incremental GIM-V は本当に有用なのか

Incremental PageRankが有用な手法であるのは、ウェブグラフの構造が、一部が変化してもそこから波及する範囲が狭いからである。
The key observation is that evolution of the Web graph is slow, with large parts of it remaining unchanged.
(Incremental Page Rank Computation on Evolving Graphs)

Incremental MethodをGIM-Vに一般化した場合に、それで適応できるアルゴリズムの実データが、実際にこのような性質を持っていない限り、大した効果がないのではないか。

論文にすることを考えるならば、Adaptive PageRank, Incremental PageRankなど、なぜ提案手法が有用であるのかセクションで述べているので、Incremental GIM-Vの場合でも、この手法を一般化しても有用であることを示す必要があるように思える。
それができないと、論文としての貢献が主張できない。
(PageRankだけ評価しても、それではIncremental PageRankの貢献およびPEGASUSの貢献を超えることができない)

2011年4月1日金曜日

SPADE:Stream Loop に関する注意

SPADEでUDOPを挟むループを記述することは可能。
ただし、あるループに含まれるオペレータのすべてが同一プロセスエレメントに含まれる場合、
正常に動作しなくなるらしい。

ループを構成するストリームの出力 submit0(), submit1() などを実行すると、そこで処理が止まってしまう。

対処法としては、適当にプロセスエレメントを分けるようにすること。
もし、同一のUDOPへのループを記述したい場合は、間に適当なFunctorを噛ませればよい。

Incremental GIM-V デバッグ中

igimv/proto3

submit_stream, ctcp_trigger.pyを実行
⇒ WorkerのprocessInput1 (stage==1) で、最初のmessageWW実行の後、処理が止まっている?

(追記)
PE の fusion を分けたらうまく動きそう。

(追記2)
4頂点5辺からなるグラフで、ページランクの計算に成功。

TODO:
・Managerの出力をみると、どこかでエラーが生じているらしい?要確認
・インクリメンタルに動作するかチェックする

(追記3 : 20110404 Mon.)
>Managerの出力をみると、どこかでエラーが生じているらしい?要確認
switch 文で break の書き忘れ。ログが冗長になるだけだったので、大した影響はなかった。
>インクリメンタルに動作するかチェックする
できた。

TODO:
・大きなグラフで実験(人工データ?作り方は、恣意的なものでよい?)
・igimv.dps をもとに gimv.dps を作成。動作比較

(追記4 : 20110404 Mon.)
頂点数10K, 辺数 448Kのグラフを、ワーカーノード4台で実行したところ、処理ができなかった。

理由を推測してみると、UDOPからUDOPに送るタプルが多すぎて、バッファが「デッドロック」のような状態に陥っているものだと思われる。

各Worker UDOPは同時に処理を開始し、一度の処理ブロックで最大で辺の数と同数のタプルを送る。
このとき、UDOPが送り先のオペレータの入力バッファが一杯になると、これ以上タプルを送れないので、バッファに空きができるまで待とうとする。
しかし、タプルを受け取ったオペレータはバッファの処理を行うことはない。
なぜならば、受け取った側のオペレータもまた、他のオペレータにタプルを送ろうとしている段階だからである。

===
MapReduceでは、MapとReduceが別スレッドで実行されている。
現状のigimv.dpsでは、Mapに相当する部分も、Reduceに相当する部分も、一つのUDOPにまとめてしまっているので、分けてしまうことで解決できるかも。

2011年3月4日金曜日

Incremental GIM-V でHADI(直径推定)を扱うべきか

⇒ 扱いたくない

直径推定をインクリメンタルに解く状況というのがあまり想定できない。

また、HADI では計算の反復回数が求める直径の値となるため、
インクリメンタルメソッドでも通常メソッドと同じ回数の反復を実行する必要がある。
計算の簡略化をもたらすためのインクリメンタルメソッドであるにもかかわらず、これではあまり効果がないように思える。

(本音を言うと、combine2履歴を実装するのが疲れる割にあまりメリットがないので、実装したくない)