並列言語Tascellによるグラフマイニングの並列化
Parallelization of Graph Mining using Parallel Language Tascell
概要
ソーシャルネットワークに対するグラフマイニングやコンピュータ将棋などでは、バックトラック探索アルゴリズムが多く用いられています。近年のプロセッサのマルチコア化に伴い、探索の並列化が高速化のために必要不可欠になっていますが、効率良い並列探索の実現は容易ではありません。そこで我々は、並列化に適した探索アルゴリズム、および効率的な動的負荷分散機能や無駄な探索を早期に打ち切るための例外処理機能を備えるタスク並列言語Tascellの開発を行っています。本発表では、各頂点がアイテムの集合を持つグラフ構造から、ある閾値以上の数の共通アイテム集合を持つ連結部分グラフを抽出するグラフマイニングの並列化について紹介します。
産業界への展開例・適用分野
本発表で紹介するグラフマイニングは、ソーシャルネットワークや生体ネットワークの分析などに応用できます。例えば、頂点が遺伝子、辺が遺伝子間の相互作用関係を示す遺伝子ネットワークにおいて、投与した薬をアイテムとして対応する頂点に付与させたグラフから共通のアイテム集合を持つ連結部分グラフを抽出できると、どの薬の組み合わせがどの遺伝子間で反応するかがわかり、創薬研究に役立ちます。また、提案する並列言語はコンピュータ将棋や制約充足問題など他の分野への応用も可能です。
研究者
| 氏名 | 専攻 | 研究室 | 役職/学年 |
|---|---|---|---|
| 奥野 伸吾 | システム科学専攻 | 中島研究室 | 博士1回生 |
| 平石 拓 | 学術情報メディアセンター | 中島研究室 | 助教 |
| 中島 浩 | 学術情報メディアセンター | 中島研究室 | 教授 |