研究領域「離散構造処理系」の概要
計算機は、産業プロセスの最適化や解析、マーケティング、バイオインフォマティクスなど、様々な情報処理に活用されており、今後、より一層の高速化・大容量化が求められています。そのためのアプローチとして、デバイス・システム技術と並んで、計算機に実装する数学的モデルを基盤とした情報処理技術、いわゆるアルゴリズム技術が重要視されています。近年の爆発的に増大している大規模データを処理するためには、膨大な離散構造データ(計算機が行う論理的な処理を表現したデータ)を簡約化し効率よく計算することが鍵となります。1986年~1990年代後半にかけて、BDD(Binary Decision Diagram:二分決定グラフ)と呼ばれる技法が開発され、基本的な離散構造の1つである論理関数の処理が大幅に高速化されました。BDDは主にハードウェア設計の検証・最適化に応用され飛躍的な成果が得られましたが、計算機の取り扱う情報が多様化・複雑化の一途をたどっている中で、より広範囲な分野に基盤的に活用できる離散構造処理系の必要性が高まっています。本研究領域は、論理関数の処理に優れたBDDと、集合データの処理に優れたZDD (Zero-Suppressed BDD; ゼロサプレス型BDD)の2つの技法を基盤として、様々な離散構造を統合的に演算処理する技法を体系化し、社会における大規模かつ多様な情報処理を統合的に高速演算処理する計算処理法の構築を目指すものです。
本研究領域の基盤となるZDDは、1993年に研究総括自身が独自に考案したBDDの進化形であり、データマイニングや知識発見への応用において顕著な有効性が示されつつあります。特に疎な組合せの集合を扱う特定分野においてはBDDに比べ100倍以上の高速化可能性を見出すなどZDDに関する知見を深化させており、これらを背景としてBDD/ZDDを基本処理系と位置付けた新たな方法論の提案に至ったものです。本研究は、離散構造を統合的に演算処理する技法を体系化し、システム検証や最適化、データマイニング、知識発見などを含む分野横断的な実問題を解くための基盤技術として構築するものです。それに向けては、まず従来の典型的な離散構造モデルに着目し、それぞれに適した固有の演算処理を構築・類型化することにより高次の演算処理系を創造します。さらに、社会的応用に向けて、具体的な実問題を対象とした性能評価を行います。そして本研究で開発した処理系の実装技術は、国内外の研究者や産業界が利用しやすい形で提供します。
本研究領域は、計算機により様々な「知識」を扱うための基盤技術そのものであり、戦略目標「多様で大規模な情報から『知識』を生産・活用するための基盤技術の創出」に資するものと期待されます。
研究総括 湊 真一 氏の略歴など
1.氏名(現職) |
湊 真一 (みなと しんいち) (北海道大学 大学院情報科学研究科 准教授) 44歳 | ||||||||||||||||||||||||||||
2.略歴 |
| ||||||||||||||||||||||||||||
3.研究分野 |
大規模論理を扱うためのデータ構造とアルゴリズム、二分決定グラフ(BDD) VLSI設計技術、データマイニングと知識発見 | ||||||||||||||||||||||||||||
4.学会活動など |
| ||||||||||||||||||||||||||||
5.業績など |
湊 真一 氏は、集合族データを効率よく表現・処理する「ゼロサプレス型二分決定グラフ」(ZDD)の考案者として世界的に知られている。この業績は、D. E. Knuthの名著 The Art of Computer Programming の最新巻(4巻第1分冊)に、日本人の研究成果としては初めて、独立した項目として詳細に取り上げられた。本項目の執筆に関しては、著者のKnuth氏から直々に校正作業への協力を依頼されている。 湊氏は京都大学大学院在学中より、当時黎明期にあったBDD技術と論理設計理論の研究を開始した。同氏は平成2年よりNTT LSI研究所にてBDD技術を応用したVLSI論理設計システムの研究開発に従事し、その間、BDDのデータ構造と大規模論理データ処理に関する多くの業績がある。平成8年にそれらの研究成果をまとめた著書「Binary Decision Diagrams and Applications for VLSI CAD」(Kluwer Academic Publishers)を出版した。本書は欧米のいくつかの理工系大学院で副教材として使用された。平成11年には、当時イリノイ大学の室賀 三郎 教授との共著により、The VLSI Handbook (IEEE Press)においてBDDの項目を執筆した。 湊氏は平成16年に北海道大学 情報科学研究科に准教授として着任した。以降、これまでのVLSI設計技術分野から、知識処理・知識発見の分野に研究範囲を拡大させ、新しい分野においてもBDD/ZDDの応用研究により著名な国際会議(IJCAI2007, DS-2006, DS-2007, PAKDD2008など)に採択される成果を挙げている。例えば、頻出アイテム集合抽出問題において当時世界最高速とされていたLCMアルゴリズム(国立情報学研究所 宇野 毅明 准教授の技術)に、ZDD技術を組み込む手法を提案し、さらに10~100倍の高速化を達成した。湊氏は、北大での最近5年間で、科学研究費3件(基盤(B)2回、萌芽1回)を研究代表者として獲得している他、研究分担者として特別推進研究(代表:有村 博紀 教授)や特定領域「情報爆発」、北大GCOE推進担当者、経産省「情報大航海」などの大型プロジェクトにも関わった経験を持つ。 このように湊氏はBDD/ZDD技術をコアとして、複数の応用分野に渡って幅広く、なおかつ国際的に認められる最先端の研究活動を行うというスタンスを確立している。 |