2011年11月17日木曜日
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日火曜日
2011年8月3日水曜日
ぱーてぃしょにんぐ、しらべもの
Spectral Clusteringについて
Data Similarity Graphというグラフを定義し、そのグラフを対象とした話。
他の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章)
2011年5月16日月曜日
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
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
など
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 は、グラフ処理としても制限がきつく、データストリーム処理としてもまだ高速化（簡略化）の余地のある手法だけど、プロトタイプとしての提案である、という方向性で書く。
これを解決するために、作業オペレータを二種類に分割するよう実装する予定である。
実装から離れて、IGIMVの研究的な意味での貢献を考えてみる必要もある。現状では、Incremental PageRank(以下、IPR)の手法をPEGASUSのグラフ計算モデル(GIM-V)に当てはめようとはしているが、これが本当に効果的であるかは自明でない。PageRankへの有用性は、当然IPRの論文で触れられているが、それ以外についてはどうなるのか。
このあたりをはっきりとしないと、研究としての貢献が主張できない。
あまり計算モデルの一般化ということを考えずに、PageRank「など」のグラフ構造解析をストリーム的に効率的に行う、という方向で研究を進めるのはどうか、と考えている。
まず、元々のIPRは、データストリーム処理のための手法ではなく、バッチ処理を効率的に行うためのものであり、IPRはActual PageRank（全体を解析する手法）と同様の、「正しい」解析結果を得られる手法である。
ストリーム的には、このIPRのように完全な解析を行うのではなく、計算の範囲を構造変化から近い頂点（距離2,3程度？適切な距離はその頂点のページランクにも依存？）に限定して行い、完全な解析はバッチ処理(IPR)に任せる、などというのはどうだろうか。
ストリーム的に行うために、オンメモリ性を考える必要もある。頂点や辺のデータはファイルシステム上に保存しておき、計算に必要のないデータはメモリにロードしないようにする。
======
頑張って書こう！
Incremental GIM-V は、グラフ処理としても制限がきつく、データストリーム処理としてもまだ高速化（簡略化）の余地のある手法だけど、プロトタイプとしての提案である、という方向性で書く。
2011年4月8日金曜日
Incremental GIM-V は本当に有用なのか
Incremental PageRankが有用な手法であるのは、ウェブグラフの構造が、一部が変化してもそこから波及する範囲が狭いからである。
Incremental MethodをGIM-Vに一般化した場合に、それで適応できるアルゴリズムの実データが、実際にこのような性質を持っていない限り、大した効果がないのではないか。
論文にすることを考えるならば、Adaptive PageRank, Incremental PageRankなど、なぜ提案手法が有用であるのかセクションで述べているので、Incremental GIM-Vの場合でも、この手法を一般化しても有用であることを示す必要があるように思える。
それができないと、論文としての貢献が主張できない。
(PageRankだけ評価しても、それではIncremental PageRankの貢献およびPEGASUSの貢献を超えることができない)
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を噛ませればよい。
ただし、あるループに含まれるオペレータのすべてが同一プロセスエレメントに含まれる場合、
正常に動作しなくなるらしい。
ループを構成するストリームの出力 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にまとめてしまっているので、分けてしまうことで解決できるかも。
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履歴を実装するのが疲れる割にあまりメリットがないので、実装したくない）
直径推定をインクリメンタルに解く状況というのがあまり想定できない。
また、HADI では計算の反復回数が求める直径の値となるため、
インクリメンタルメソッドでも通常メソッドと同じ回数の反復を実行する必要がある。
計算の簡略化をもたらすためのインクリメンタルメソッドであるにもかかわらず、これではあまり効果がないように思える。
（本音を言うと、combine2履歴を実装するのが疲れる割にあまりメリットがないので、実装したくない）
2011年2月28日月曜日
Incremental PageRank , スケールの話
(20110301 Tue. 追記)
ページランクを正しく求める方法では、反復計算の初期値によらずただ一つのページランク（固有ベクトル）に収束するのだから、「頂点の削除」を扱わないのならば、
・元々あった頂点 ⇒ 値を変更しない
・新たに追加された頂点 ⇒ 初期値0 (id=0の頂点のみ初期値1)
で計算すれば、べき乗法で、ページランクの総和が1になるやり方でも、正しくページランクが求まるはず。
ただし、総和が1になるやり方では、ランダムジャンプの遷移によるページランクの値が
(1-c)/n となり、このnの値が変わるので、計算が収束した頂点も結局計算しなおす必要が生じるかもしれない。
そもそも、どこにもリンクしていないページの存在を正しく扱うと、そのページからは必ずランダムジャンプを行うように扱う必要が生じるため、
そのような頂点が発生すると、計算が収束した頂点のページランクにも影響が生じるので結局計算しなおす必要があるのかも？
(どこにもリンクしていない頂点が少ない(and,or)ページランクが小さい場合であれば、それによるページランクへの影響は多くの場合スレッショルド未満かもしれないが)
収束判定 (総和が1の場合) : abs(PR_new-PR_old)/PR_old < threashold (where threashold = 0.001)
Adaptive PageRankでのやり方
(20110228 Mon.)
Incremental PageRankについて、前回の全体ミーティングで、前のスライドのスケールのやり方では各ページのページランクの総和を取っても 1 にならない、と雁瀬君から指摘を受けましたが、その後、雁瀬君との議論により、総和が 1 になるようなスケールの仕方（というか、直接的にはスケールしなくて良い方法）を見つけました。
まず、本来のページランクでは総和が 1 になるようになっていますが、ここでは総和が n (頂点数) となるように全体を拡大します。
ΣVi = n
また、グラフの構造の変化として、辺の追加と削除、頂点の追加のみを扱い、「頂点の削除」は扱わないものとします。
Incremental PageRankの計算で扱う頂点は以下の三種類に分けられます。
（計算時の分け方 Vul, Vb, Vur, Vcr とは異なる）
(1) 元からあった頂点で、スケールのみでよい (Vul, Vb)
(2) 元からあった頂点で、再計算が必要
(3) 追加された頂点で、再計算が必要
このうち、(1)と(2)はすでにページランクが割り当てられていて、その総和は(1)と(2)の頂点数と一致します。
頂点が追加されたので、その数だけ全体のページランクの総和も増える必要があります。そこで、(3)の頂点の初期ページランクとして1 を設定します。
ここで、(1)(2)(3)に対してページランク計算を実行すれば、その総和は『どこにもリンクしていない頂点は存在しない』という仮定の下であれば、頂点数と一致します。
このうち、(1)の部分はページランク計算の際に値が変わらない（はずな）ので、ページランク計算の際には(2)(3)にページランク遷移を送るだけでよい(Vb)ので、処理を簡略化できます。
本来必要だったスケール処理部分は、PageRankの値を常に「頂点数」倍にした値で計算することによって省略されます。
なお、このページランクの計算方法では、全体が強連結であるとは限らないという仮定の下で計算しているので、計算の初期値によって収束する値が異なる可能性があります。
ページランクを正しく求める方法では、反復計算の初期値によらずただ一つのページランク（固有ベクトル）に収束するのだから、「頂点の削除」を扱わないのならば、
・元々あった頂点 ⇒ 値を変更しない
・新たに追加された頂点 ⇒ 初期値0 (id=0の頂点のみ初期値1)
で計算すれば、べき乗法で、ページランクの総和が1になるやり方でも、正しくページランクが求まるはず。
ただし、総和が1になるやり方では、ランダムジャンプの遷移によるページランクの値が
(1-c)/n となり、このnの値が変わるので、計算が収束した頂点も結局計算しなおす必要が生じるかもしれない。
そもそも、どこにもリンクしていないページの存在を正しく扱うと、そのページからは必ずランダムジャンプを行うように扱う必要が生じるため、
そのような頂点が発生すると、計算が収束した頂点のページランクにも影響が生じるので結局計算しなおす必要があるのかも？
(どこにもリンクしていない頂点が少ない(and,or)ページランクが小さい場合であれば、それによるページランクへの影響は多くの場合スレッショルド未満かもしれないが)
収束判定 (総和が1の場合) : abs(PR_new-PR_old)/PR_old < threashold (where threashold = 0.001)
Adaptive PageRankでのやり方
(20110228 Mon.)
Incremental PageRankについて、前回の全体ミーティングで、前のスライドのスケールのやり方では各ページのページランクの総和を取っても 1 にならない、と雁瀬君から指摘を受けましたが、その後、雁瀬君との議論により、総和が 1 になるようなスケールの仕方（というか、直接的にはスケールしなくて良い方法）を見つけました。
まず、本来のページランクでは総和が 1 になるようになっていますが、ここでは総和が n (頂点数) となるように全体を拡大します。
ΣVi = n
また、グラフの構造の変化として、辺の追加と削除、頂点の追加のみを扱い、「頂点の削除」は扱わないものとします。
Incremental PageRankの計算で扱う頂点は以下の三種類に分けられます。
（計算時の分け方 Vul, Vb, Vur, Vcr とは異なる）
(1) 元からあった頂点で、スケールのみでよい (Vul, Vb)
(2) 元からあった頂点で、再計算が必要
(3) 追加された頂点で、再計算が必要
このうち、(1)と(2)はすでにページランクが割り当てられていて、その総和は(1)と(2)の頂点数と一致します。
頂点が追加されたので、その数だけ全体のページランクの総和も増える必要があります。そこで、(3)の頂点の初期ページランクとして1 を設定します。
ここで、(1)(2)(3)に対してページランク計算を実行すれば、その総和は
このうち、(1)の部分はページランク計算の際に値が変わらない（はずな）ので、ページランク計算の際には(2)(3)にページランク遷移を送るだけでよい(Vb)ので、処理を簡略化できます。
本来必要だったスケール処理部分は、PageRankの値を常に「頂点数」倍にした値で計算することによって省略されます。
2011年2月8日火曜日
Incremental GIM-V 必要メモリ概算
頂点id の型を Long (int64_t) とする。
頂点id を0以上の整数として扱うならば、扱うことのできる頂点数の上限は
2^64 ≒ 9.22 エクサ個となる。
SPADEの整数型に Unsigned なものってないんですかね。
===
SPADEのリファレンスをよく見てみると、"each list is limited to 2^32 - 1 entries"
とある。RWRとHADIでは頂点の値の型およびcombine2の値の型にリストを使うので、
頂点数の上限は 2^32 - 1 ≒ 4.29 ギガ個となる。
===
各アルゴリズムで必要とするメモリの大きさを概算してみる。
頂点数を N 辺数を E と置く。
PageRankの場合、
辺の値の型は Double (8 Bytes)、これに始点id (Long ;8 Bytes) 終点id (Long)
を足すので一辺あたり 24 Bytes。辺全体で 24*E Bytes。
頂点の値の型は Double。頂点全体で 8*N Bytes。
combine2の最終値を保存しておく必要がある。
combine2の値の型は Double、これに辺の終点id(Long)を足して、辺全体で 16*E Bytes。
各頂点のグラフ分割(Byte)も保存する。頂点全体で N Bytes。
あとは頂点数や辺数に依存しないデータのみなので省略。
合計すると 32*E + 9*N Bytes
頂点数が 1Mi 辺数が 100Mi とすると全体で 3209 MiB。
===
RWRの場合、
辺の値の型 : Double
辺全体 : 24*E Bytes
頂点の値の型 : DoubleList (要素数N)
頂点全体 : 24*N*N Bytes
combine2の値の型 : DoubleList (要素数N)
combine2最終値全体 : (8*N + 8)*E Bytes
グラフ分割情報全体 : N Bytes
合計 : 8*N*E + 24*N*N + 32*E + N Bytes
頂点数が 1Mi 辺数が 100Mi とすると全体で 824 TiB (+ 3201 MiB)。大きすぎ。
===
TODO:HADI, HCCについて書く。
HADIはByteListの履歴が必要となる。非常に大きくなると思う。
頂点id を0以上の整数として扱うならば、扱うことのできる頂点数の上限は
2^64 ≒ 9.22 エクサ個となる。
SPADEの整数型に Unsigned なものってないんですかね。
===
SPADEのリファレンスをよく見てみると、"each list is limited to 2^32 - 1 entries"
とある。RWRとHADIでは頂点の値の型およびcombine2の値の型にリストを使うので、
頂点数の上限は 2^32 - 1 ≒ 4.29 ギガ個となる。
===
各アルゴリズムで必要とするメモリの大きさを概算してみる。
頂点数を N 辺数を E と置く。
PageRankの場合、
辺の値の型は Double (8 Bytes)、これに始点id (Long ;8 Bytes) 終点id (Long)
を足すので一辺あたり 24 Bytes。辺全体で 24*E Bytes。
頂点の値の型は Double。頂点全体で 8*N Bytes。
combine2の最終値を保存しておく必要がある。
combine2の値の型は Double、これに辺の終点id(Long)を足して、辺全体で 16*E Bytes。
各頂点のグラフ分割(Byte)も保存する。頂点全体で N Bytes。
あとは頂点数や辺数に依存しないデータのみなので省略。
合計すると 32*E + 9*N Bytes
頂点数が 1Mi 辺数が 100Mi とすると全体で 3209 MiB。
===
RWRの場合、
辺の値の型 : Double
辺全体 : 24*E Bytes
頂点の値の型 : DoubleList (要素数N)
頂点全体 : 24*N*N Bytes
combine2の値の型 : DoubleList (要素数N)
combine2最終値全体 : (8*N + 8)*E Bytes
グラフ分割情報全体 : N Bytes
合計 : 8*N*E + 24*N*N + 32*E + N Bytes
頂点数が 1Mi 辺数が 100Mi とすると全体で 824 TiB (+ 3201 MiB)。大きすぎ。
===
TODO:HADI, HCCについて書く。
HADIはByteListの履歴が必要となる。非常に大きくなると思う。
2011年2月7日月曜日
StreamGraph テクニカルチャレンジ（およびスライド修正点）
■ テクニカルチャレンジ
>GPU
>頂点配置の最適化
ハッシュ ⇒ マイグレーション 頂点の配置についてどこが管理するか
非対称構成などで特定のノードが遅くなる場合などにも配置最適化は有効
>フォールトトレラント
現状、GAが1つでも落ちると処理が次のステップに移れなくなりシステムが止まってしまう
>解析開始の最適タイミング
どのくらい構造変化が生じたら解析を始めるべきか
■スライド修正点
>システム全体が頂点数を知らないといけない
PageRank → スケールに必要
RWR, HADI → 頂点値とcombine2の次元数の決定に必要
解析開始トリガを通じて、グラフの総頂点数をシステムに通知する、など
>HADIについて、履歴がまだ残っている（収束していない）場合に解析が終わってしまう可能性がある
履歴が収束するまではGIM-V反復計算を行うようにする
>名称変更 : add_or_remove ⇒ update_or_remove
値もString("add", "remove")からint(1,0)などに変更
>状態遷移図で「前処理」と「GIM-V計算」の部分の色を分けてわかりやすくする
>表記変更 : 「計算内容」 ⇒ 「グラフ分割」
Q : 構造変化 | b : 変化なし、ボーダー | u : 変化なし
■とりあえず
>プロトタイプ実装しよう
>GPU
>頂点配置の最適化
ハッシュ ⇒ マイグレーション 頂点の配置についてどこが管理するか
非対称構成などで特定のノードが遅くなる場合などにも配置最適化は有効
>フォールトトレラント
現状、GAが1つでも落ちると処理が次のステップに移れなくなりシステムが止まってしまう
>解析開始の最適タイミング
どのくらい構造変化が生じたら解析を始めるべきか
■スライド修正点
>システム全体が頂点数を知らないといけない
PageRank → スケールに必要
RWR, HADI → 頂点値とcombine2の次元数の決定に必要
解析開始トリガを通じて、グラフの総頂点数をシステムに通知する、など
>HADIについて、履歴がまだ残っている（収束していない）場合に解析が終わってしまう可能性がある
履歴が収束するまではGIM-V反復計算を行うようにする
>名称変更 : add_or_remove ⇒ update_or_remove
値もString("add", "remove")からint(1,0)などに変更
>状態遷移図で「前処理」と「GIM-V計算」の部分の色を分けてわかりやすくする
>表記変更 : 「計算内容」 ⇒ 「グラフ分割」
Q : 構造変化 | b : 変化なし、ボーダー | u : 変化なし
■とりあえず
>プロトタイプ実装しよう
2011年1月17日月曜日
個別ミーティング 2011.01.17 Mon.
・スライドにまとめる
・アルゴリズム確認、実装法について言及 : RWR, HCC, (HADI, PageRank)
・Incremental GIM-V インターフェース修正
（combine2_unchanged() を削除）
（combine2の履歴と最終結果だけのどちらを残すか選ばせるスイッチに）
・ストーリー
ストリームでインクリメンタルなグラフ処理がしたい
→ GIM-Vというグラフ処理のためのフレームがある
→ それをストリーム向けに拡張 ⇒ Incremental GIM-V
・SPADE実装に向けて、データフロー図を考えてみる (UDOPなど)
====
いろいろ他にやることもあるけど、スライドにまとめるところまでは今月中にやってしまいたい
・アルゴリズム確認、実装法について言及 : RWR, HCC, (HADI, PageRank)
・Incremental GIM-V インターフェース修正
（combine2_unchanged() を削除）
（combine2の履歴と最終結果だけのどちらを残すか選ばせるスイッチに）
・ストーリー
ストリームでインクリメンタルなグラフ処理がしたい
→ GIM-Vというグラフ処理のためのフレームがある
→ それをストリーム向けに拡張 ⇒ Incremental GIM-V
・SPADE実装に向けて、データフロー図を考えてみる (UDOPなど)
====
いろいろ他にやることもあるけど、スライドにまとめるところまでは今月中にやってしまいたい
2011年1月12日水曜日
続き : GIM-V PageRankへのIncremental PageRankの応用
前回の続き
======
HADI(直径推定アルゴリズム)への応用を考える。
グラフ構造変更前に求めた直径の値を(d_old)と置く。
グラフ構造変更後、GQ（前回を参照）に対してHADIを実行し、求まった直径の値を(d_part)と置く。
直径の値は max(d_old, d_part) となる。
ここでは、PageRankと異なり、combineAll()の計算対象に他の値を与える必要はない。
（あるいは、combineAllはビット論理和を求める演算なので、値として 0 を与える）
直径推定の場合、メッセージとして送られる値のデータ量が非常に大きくなるので
（グラフの頂点数を N(V) とおくと、1つのメッセージの値には N(V) ビット以上必要）
Incremental GIM-Vによる差分更新であれば、計算対象となるグラフが小さくて済むためネットワークコストも下がることになる。
======
PageRank, RWR, HADI まで応用できそう。
オリジナルのGIM-Vでは combine2(), combineAll(), assign(), および反復の終了条件などをアルゴリズム毎に定義する必要がある。
Incremental GIM-Vではそれに加えて、変化しない点に対する処理として、
スケール処理を行う scale_unchanged(), 変化する点のcombineAll の計算対象として加える値を決める combine2_unchanged() をアルゴリズム毎に定義させる。
（というようなアルゴリズムインターフェースにしたい）
======
スライド : Incremental GIM-V_memo_20110112.pptx
TODO: 非GIM-V なアルゴリズムにはIncremental PageRankの考え方は使えるか？（クラスタリングなど）
======
HADI(直径推定アルゴリズム)への応用を考える。
グラフ構造変更前に求めた直径の値を(d_old)と置く。
グラフ構造変更後、GQ（前回を参照）に対してHADIを実行し、求まった直径の値を(d_part)と置く。
直径の値は max(d_old, d_part) となる。
ここでは、PageRankと異なり、combineAll()の計算対象に他の値を与える必要はない。
（あるいは、combineAllはビット論理和を求める演算なので、値として 0 を与える）
直径推定の場合、メッセージとして送られる値のデータ量が非常に大きくなるので
（グラフの頂点数を N(V) とおくと、1つのメッセージの値には N(V) ビット以上必要）
Incremental GIM-Vによる差分更新であれば、計算対象となるグラフが小さくて済むためネットワークコストも下がることになる。
======
PageRank, RWR
オリジナルのGIM-Vでは combine2(), combineAll(), assign(), および反復の終了条件などをアルゴリズム毎に定義する必要がある。
Incremental GIM-Vではそれに加えて、変化しない点に対する処理として、
スケール処理を行う scale_unchanged(), 変化する点のcombineAll の計算対象として加える値を決める combine2_unchanged() をアルゴリズム毎に定義させる。
（というようなアルゴリズムインターフェースにしたい）
======
スライド : Incremental GIM-V_memo_20110112.pptx
TODO: 非GIM-V なアルゴリズムにはIncremental PageRankの考え方は使えるか？（クラスタリングなど）
2011年1月7日金曜日
GIM-V PageRankへのIncremental PageRankの応用
GIM-V PageRankへのIncremental PageRankの応用を考える。
3節のStep3までは同じようにやればよい。
Step4を実行することを考える。
Vbに含まれる頂点のPageRankはこの時点で定まっていて、変更の必要はない。
VQ : 構造変化が生じた頂点、およびそこからたどれる頂点の集合
VQと、VQ内を結ぶ辺(EQ)からなるグラフ(GQ)に対してGIM-V PageRank(+拡張)を実行する。（論文中のEQ,GQの定義とは異なる点に注意）
GIM-V PageRankの手法では、ページ遷移を表わす重みをcombine2()で計算、その重みの合計からPageRankの計算をcombineAll()で行う。
combine2()は、GQ内の値からしか計算されない。しかし、VQ内の頂点のPageRankの計算はcombine2()の結果だけでなく、Vbからの重みも加味して行う必要がある。そこで、GIM-V PageRankに拡張を施す。すなわち、combine2()の結果に加えて、Vbからの重みもcombineAll()の計算対象にするように拡張すればよい。
======
Incremental PageRankの手法をGIM-V PageRankに応用する手法はわかったが、GIM-V一般には応用できるだろうか。GIM-Vによる他のアルゴリズムをまだちゃんと理解していないので、それも調べる必要がある。RWRには適用できそう。
Incremental PageRankの手法は、PageRankの計算構造に着目した最適化によるものなので、グラフ処理一般にそのまま応用できるだろうか。
======
Incremental PageRank
グラフ構造が変化（※1）したときに、
・PageRankが変化せず（※2）、他の頂点にも影響を及ぼさない頂点
・PageRankは変化しないが、他の頂点のPageRankの計算に必要な頂点
・PageRankが変化する点（構造が変化した点、変化の影響を受ける点）
に分けて計算を行う。
（※1）グラフ構造の変化として、PageRankの場合、（頂点追加、頂点削除、辺追加、辺削除）の4通りが考えられる。辺の追加と削除の場合、その辺で繋がる頂点の2つともを「構造が変化した点」として扱う。（はず。論文中では明記されていない…と思う。）
（※2）実際には、頂点数の変化に伴いPageRankの値に係数をかけるという、簡単な再計算を行う必要はある。
3節のStep3までは同じようにやればよい。
Step4を実行することを考える。
Vbに含まれる頂点のPageRankはこの時点で定まっていて、変更の必要はない。
VQ : 構造変化が生じた頂点、およびそこからたどれる頂点の集合
VQと、VQ内を結ぶ辺(EQ)からなるグラフ(GQ)に対してGIM-V PageRank(+拡張)を実行する。（論文中のEQ,GQの定義とは異なる点に注意）
GIM-V PageRankの手法では、ページ遷移を表わす重みをcombine2()で計算、その重みの合計からPageRankの計算をcombineAll()で行う。
combine2()は、GQ内の値からしか計算されない。しかし、VQ内の頂点のPageRankの計算はcombine2()の結果だけでなく、Vbからの重みも加味して行う必要がある。そこで、GIM-V PageRankに拡張を施す。すなわち、combine2()の結果に加えて、Vbからの重みもcombineAll()の計算対象にするように拡張すればよい。
======
Incremental PageRankの手法をGIM-V PageRankに応用する手法はわかったが、GIM-V一般には応用できるだろうか。GIM-Vによる他のアルゴリズムをまだちゃんと理解していないので、それも調べる必要がある。RWRには適用できそう。
Incremental PageRankの手法は、PageRankの計算構造に着目した最適化によるものなので、グラフ処理一般にそのまま応用できるだろうか。
======
Incremental PageRank
グラフ構造が変化（※1）したときに、
・PageRankが変化せず（※2）、他の頂点にも影響を及ぼさない頂点
・PageRankは変化しないが、他の頂点のPageRankの計算に必要な頂点
・PageRankが変化する点（構造が変化した点、変化の影響を受ける点）
に分けて計算を行う。
（※1）グラフ構造の変化として、PageRankの場合、（頂点追加、頂点削除、辺追加、辺削除）の4通りが考えられる。辺の追加と削除の場合、その辺で繋がる頂点の2つともを「構造が変化した点」として扱う。（はず。論文中では明記されていない…と思う。）
（※2）実際には、頂点数の変化に伴いPageRankの値に係数をかけるという、簡単な再計算を行う必要はある。
登録:
投稿 (Atom)