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