平成21（2009）年度　一般研究１実施報告書

課題番号	21−共研−1023	分野分類		統計数理研究所内分野分類		i
				主要研究分野分類		2
研究課題名	効率的な並列データマイニングアルゴリズムの開発
フリガナ 代表者氏名	ウノ　タケアキ 宇野　毅明		ローマ字		Uno Takeaki
所属機関	国立情報学研究所
所属部局	情報学プリンシプル研究系
職　　名	准教授

研究目的と成果（経過）の概要

頻出パターン発見問題は、データベースの多くの項目に含まれるようなパターンを列挙する問題であり、データマイニング分野における中心的な問題である。特に各項目がアイテム集合の部分集合であり、パターンもアイテムの集合であるような問題は頻出集合発見と呼ばれ、頻出パターン発見問題の中でも基礎的であり、他の様々な求解手法に用いられている。頻出集合は一般に多くの解を出力するために計算時間が非常にかかり、さらに他の問題で利用する場合には探索する解の数はさらに増える傾向がある。1台のコンピュータを用いて求解アルゴリズムは、入出力がボトルネックになる、という意味でほぼ最適なレベルまで到達しているため、さらなる改良には並列計算が必須である。本研究では、現在最速なアルゴリズムの一つであるLCMの並列化を研究する。頻出パターン発見問題は通常多くのメモリを使用するため、単純に並列化を行なっただけではメモリ不足によりパフォーマンスの大幅な低下が起こる。そこでメモリを効率良く利用し、並列化に伴うオーバーヘッドを軽くするような並列化手法を研究すると共に、その実装の効率性をスーパーコンピュータを用いて評価する。
　今回の研究では、LCMの並列化を実装して評価する段階まで進めることはできたが、残念ながら当初計画していた統計数理研究所の保有するスーパーコンピュータに対応した実装の開発を行うところまでは作業がおいつかず、実験を行うことができなかった。過去の類似研究が統数研のスーパーコンピュータと同じものを利用していたため、的確な比較ができるものともくろんでいたが、残念ながらその機種は昨年12月に使用停止となってしまった。今後は、他のスーパーコンピュータに対応した、効率良い実装を構築することで、並列データマイニングアルゴリズムの構築法に関する知見を明らかにしていきたいと考えている。

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

Benjamin Negrevergne, Jean-Francois Mehaut, Alexandre Termier, Takeaki Uno: Decouverte d'itemsets frequents fermes sur architecture multicoeurs. EGC 2010: 465-470

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

研究参加者一覧
氏名	所属機関
Alexandre Termier	フランス・ジョセフフーリエ大学
Benjamin Negrevergne	フランス・ジョセフフーリエ大学