研究領域の概要及び研究総括の略歴

　計算機は、産業プロセスの最適化や解析、マーケティング、バイオインフォマティクスなど、様々な情報処理に活用されており、今後、より一層の高速化・大容量化が求められています。そのためのアプローチとして、デバイス・システム技術と並んで、計算機に実装する数学的モデルを基盤とした情報処理技術、いわゆるアルゴリズム技術が重要視されています。近年の爆発的に増大している大規模データを処理するためには、膨大な離散構造データ（計算機が行う論理的な処理を表現したデータ）を簡約化し効率よく計算することが鍵となります。１９８６年～１９９０年代後半にかけて、BDD（Binary Decision Diagram:二分決定グラフ）と呼ばれる技法が開発され、基本的な離散構造の１つである論理関数の処理が大幅に高速化されました。BDDは主にハードウェア設計の検証・最適化に応用され飛躍的な成果が得られましたが、計算機の取り扱う情報が多様化・複雑化の一途をたどっている中で、より広範囲な分野に基盤的に活用できる離散構造処理系の必要性が高まっています。
　本研究領域は、論理関数の処理に優れたBDDと、集合データの処理に優れたZDD (Zero-Suppressed BDD; ゼロサプレス型BDD）の２つの技法を基盤として、様々な離散構造を統合的に演算処理する技法を体系化し、社会における大規模かつ多様な情報処理を統合的に高速演算処理する計算処理法の構築を目指すものです。
　本研究領域の基盤となるZDDは、１９９３年に研究総括自身が独自に考案したBDDの進化形であり、データマイニングや知識発見への応用において顕著な有効性が示されつつあります。特に疎な組合せの集合を扱う特定分野においてはBDDに比べ１００倍以上の高速化可能性を見出すなどZDDに関する知見を深化させており、これらを背景としてBDD/ZDDを基本処理系と位置付けた新たな方法論の提案に至ったものです。本研究は、離散構造を統合的に演算処理する技法を体系化し、システム検証や最適化、データマイニング、知識発見などを含む分野横断的な実問題を解くための基盤技術として構築するものです。それに向けては、まず従来の典型的な離散構造モデルに着目し、それぞれに適した固有の演算処理を構築・類型化することにより高次の演算処理系を創造します。さらに、社会的応用に向けて、具体的な実問題を対象とした性能評価を行います。そして本研究で開発した処理系の実装技術は、国内外の研究者や産業界が利用しやすい形で提供します。
　本研究領域は、計算機により様々な「知識」を扱うための基盤技術そのものであり、戦略目標「多様で大規模な情報から『知識』を生産・活用するための基盤技術の創出」に資するものと期待されます。

１．氏名（現職）	湊 真一　（みなと しんいち） （北海道大学 大学院情報科学研究科　准教授）　４４歳
２．略歴	平成２年３月 京都大学 大学院工学研究科 情報工学専攻　修士課程　修了 平成２年４月 日本電信電話（株）入社。同社ＬＳＩ研究所　研究員 平成７年３月 京都大学 大学院工学研究科 情報工学専攻　博士課程（社会人）修了　博士（工学） 平成９年１月～１２月 スタンフォード大学 計算機科学科　客員研究員 平成１１年２月 ＮＴＴ未来ねっと研究所 主任研究員 平成１６年４月 北海道大学 大学院情報科学研究科 コンピュータサイエンス専攻　助教授 （平成１９年　同 准教授）
３．研究分野	大規模論理を扱うためのデータ構造とアルゴリズム、二分決定グラフ(ＢＤＤ) ＶＬＳＩ設計技術、データマイニングと知識発見
４．学会活動など	平成１１年～１６年、１９年 情報処理学会論文誌 設計自動化特集号 編集委員 平成１２年～１５年 情報処理学会論文誌 編集委員 平成１８年～２１年 電子情報通信学会英文論文誌 ＶＬＳＩ設計技術特集号 編集委員 平成１９年～ 電子情報通信学会 情報ネットワーク研究会　専門委員 平成２１年 電子情報通信学会論文誌 情報爆発特集号 編集委員 国際学会などの組織委員 平成９年～１１年 International Conference on Computer-Aided Design(ICCAD) PC member 平成１０年～１７年 Design Automation and Test, Europe (DATE) PC member 平成１０年～１３年、１８年、１９年 Asia and South-Pacific Design Automation Conference (ASPDAC) TPC member 平成１３年～１５年 Design Automation Conference(DAC) PC member 平成２０年 International workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery (ALSIP 2008)　Workshop Chair 平成２０年～２２年 ASPDAC TPC Sub-topic Chair 平成２１年 SIAM International Conference on Data Mining(SDM) PC member 平成２１年 Asian Conference on Machine Learning (ACML) PC member
５．業績など	湊 真一　氏は、集合族データを効率よく表現・処理する「ゼロサプレス型二分決定グラフ」(ＺＤＤ)の考案者として世界的に知られている。この業績は、D. E. Knuthの名著 The Art of Computer Programming の最新巻(４巻第１分冊)に、日本人の研究成果としては初めて、独立した項目として詳細に取り上げられた。本項目の執筆に関しては、著者のKnuth氏から直々に校正作業への協力を依頼されている。 　湊氏は京都大学大学院在学中より、当時黎明期にあったＢＤＤ技術と論理設計理論の研究を開始した。同氏は平成２年よりＮＴＴ ＬＳＩ研究所にてＢＤＤ技術を応用したＶＬＳＩ論理設計システムの研究開発に従事し、その間、ＢＤＤのデータ構造と大規模論理データ処理に関する多くの業績がある。平成８年にそれらの研究成果をまとめた著書「Binary Decision Diagrams and Applications for VLSI CAD」(Kluwer Academic Publishers)を出版した。本書は欧米のいくつかの理工系大学院で副教材として使用された。平成１１年には、当時イリノイ大学の室賀 三郎　教授との共著により、The VLSI Handbook (IEEE Press)においてＢＤＤの項目を執筆した。 　湊氏は平成１６年に北海道大学 情報科学研究科に准教授として着任した。以降、これまでのＶＬＳＩ設計技術分野から、知識処理・知識発見の分野に研究範囲を拡大させ、新しい分野においてもＢＤＤ／ＺＤＤの応用研究により著名な国際会議（IJCAI2007, DS-2006, DS-2007, PAKDD2008など）に採択される成果を挙げている。例えば、頻出アイテム集合抽出問題において当時世界最高速とされていたＬＣＭアルゴリズム（国立情報学研究所　宇野 毅明　准教授の技術）に、ＺＤＤ技術を組み込む手法を提案し、さらに１０～１００倍の高速化を達成した。湊氏は、北大での最近５年間で、科学研究費３件（基盤(Ｂ)２回、萌芽１回）を研究代表者として獲得している他、研究分担者として特別推進研究（代表：有村 博紀　教授）や特定領域「情報爆発」、北大ＧＣＯＥ推進担当者、経産省「情報大航海」などの大型プロジェクトにも関わった経験を持つ。 　このように湊氏はＢＤＤ／ＺＤＤ技術をコアとして、複数の応用分野に渡って幅広く、なおかつ国際的に認められる最先端の研究活動を行うというスタンスを確立している。