The Art of Algorithms for Massive Data Processing
ERATO湊離散構造処理系プロジェクトシンポジウム（第2回）
ERATO湊離散構造処理系プロジェクトシンポジウム（第2回）
日時：3月2日（水）14:30-17:30
会場：第2イベント会場 （西5号館講義棟 2F W521）
【セッション概要】まずERATO湊離散構造処理系プロジェクトの位置づけ、研究領域、最近の状況について述べる。次に、本プロジェクトの重要課題の１つである、超大規模データを扱うためのアルゴリズム技術に関する最近の話題を中心とした基調講演を行う。引き続き、ERATOメンバおよび共同研究関係者の最新の研究内容5～10件をポスターセッションにより紹介し、参加者同士の実質的な技術討論を行うことにより、本研究分野のさらなる発展を目指す。
| 司会：山中 克久 （電気通信大学 大学院情報システム学研究科 助教） | |
 |
【略歴】2007年 群馬大学大学院 工学研究科 博士後期課程修了 博士(工学)。2008年 電気通信大学 大学院情報システム学研究科 助教。専門は、アルゴリズム理論、グラフ理論。 |
| 14:30-14:35 オープニング | |
| 14:35-14:55 講演-1 ERATOプロジェクトの立ち上げと研究の進展状況について |
|
| 湊 真一 （北海道大学 大学院情報科学研究科 教授） | |
| 【講演概要】計算機は、産業プロセスの最適化や解析、マーケティング、バイオインフォマティクスなど、様々な情報処理に活用されているが、近年の爆発的に増大している大規模データを処理するためには、計算機ハードウェアの高速化だけでなく、膨大な離散構造データを数学的に簡約化し効率よく計算する技術の重要性が高まっている。今年度より開始されたERATO湊離散構造処理系プロジェクトでは、基本的な離散構造である論理関数を処理するBDD（Binary Decision Diagram）と、その進化形であるZDD (Zero-Suppressed BDD）を基盤とした離散構造処理系の研究に取り組んでいる。本講演では、ERATO湊離散構造処理系プロジェクトの初年度からの立ち上げ状況について述べ、最近の研究の進展状況について説明する。 |
|
 |
【略歴】1988年京都大学工学部情報工学科卒業、1990年同大学大学院修士課程、1995年博士課程（社会人）修了。1990年日本電信電話（株）入社。NTT研究所にて大規模論理データ処理アルゴリズムの研究に従事。2004年北海道大学大学院情報科学研究科 助教授。2010年10月より同教授。現在に至る。2009年10月よりJST ERATO湊離散構造処理系プロジェクト研究総括（兼務）。BDD(二分決定グラフ)を用いた大規模離散構造の演算処理に興味を持つ。情報処理学会, 電子情報通信学会, 人工知能学会、IEEE各会員. 博士（工学）。 |
| 14:55-15:25 講演-2-1 複合ソート法による高速な全ペア類似度検索 | |
| 津田 宏治 （独立行政法人産業技術総合研究所 生命情報工学研究センター 主任研究員） | |
| 【講演概要】近年、画像や信号などを、数十ビット程度のスケッチとよばれるビット列で表す手法が、多く提案されている。 ここから、半教師つき学習などに必要な類似度ネットワークを作成するには、ハミング距離の意味で近いペアを網羅的に発見する必要がある。 しかし、全てのペアに関して距離を計算する方法は遅すぎ、三角不等式を用いて 枝刈りをする方法を用いても十分な速度が得られない。 本発表では、アイテムセットマイニングに用いられるPattern Growth法と、基数 ソートを組合わせた複合ソート法という手法を紹介し、160万サンプルの画像 データに適用して、cover tree, Lanczos bisectionなどの他手法よりも、大幅 に高速であることを示す。 特に、Locality sensitive hashingを用いてスケッチを作成した際の平均的な偽陰性確率（見逃しの確率）や、重複した発見を避けるための工夫についても述べる。 |
|
 |
【略歴】1994年京都大学工学部情報工学科卒業。1996年同大学院工学研究科情報工学専攻修士課程修了。1998年同博士課程修了、電子技術総合研究所入所。2000年独GMD FIRST客員研究員。2003-2004独Max Planck研究所研究員。2006-2008同チームリーダー。博士（工学）。現在、産業技術総合研究所生命情報工学研究センター機械学習研究班長、主任研究員。JST-ERATO湊離散構造処理系プロジェクトサブリーダー兼任。国立情報学研究所客員准教授（最先端研究開発プログラム）。 |
| 15:25-15:55 講演-2-2 クリークマイニングとその応用 | |
| 宇野 毅明 （国立情報学研究所 情報学プリンシプル研究系 准教授） | |
| 【講演概要】全ての頂点が枝で繋がれた部分グラフはクリークと呼ばれる。クリークは密な部分構造を表す自然なモデルであるため、データマイニングやデータベースの分野で盛んに利用されてきた。一方、アルゴリズム分野では、長らくクリークは最適化の対象であったが、2000年以後、現実的な時間で動く極大解列挙アルゴリズムが相次いで発見された。それにより、現実の巨大データに対する解析が実際に可能となった。本稿では発表者らが開発した極大クリーク列挙アルゴリズムの概略と、それを用いた全く新しいタイプのパターンマイニング手法を紹介する。 |
|
 |
【略歴】1998年3月東京工業大学総合理工学研究科博士課程終了、博士(理学)を取得。1998年4月東京工業大学経営工学専攻助手着任、2001年2月国立情報学研究所助教授着任。2005年5月より2006年8月までスイス連邦工科大学に滞在。現在、情報学プリンシプル研究系准教授。日本オペレーションズリサーチ学会、情報処理学会、電気情報通信学会に所属。専門はアルゴリズム理論、特に離散アルゴリズム、列挙アルゴリズム、計算量理論、組合せ最適化、データマイニング・データベースにおけるアルゴリズム。2010年文部科学大臣表彰 科学技術部門 若手科学者賞受賞。 |
| 15:55-17:30 ポスターセッション | |
| 【セッション概要】ERATOメンバおよび連携・共同研究関係者の最新の研究内容をポスター形式で紹介する。ポスターセッションに入る前に、各ポスターの概要を簡単に紹介し、その後、ポスターにて自由討論を行う。来場者と発表者の相互の活気ある自由討論により、それぞれの研究の発展を狙うとともに、離散構造処理系をベースとした分野横断的な研究者コミュニティの一層の強化を図る。 |
|
| 【ポスター発表予定者】 定兼 邦彦 （国立情報学研究所） 野中 良哲 （九州大学） 山中 克久 （電気通信大学） 岸本 章宏 （東京工業大学） 猪口 明博 （大阪大学） 櫻井 祐子 （JST ERATO） 吉仲 亮 （JST ERATO） 川原 純 （JST ERATO） 斉藤 寿樹 （JST ERATO） 田部井 靖生 （JST ERATO） |
|
