このページの先頭です

メニューを飛ばして本文を読む

ここから本文です

サイト内の現在位置

教員紹介

戸田 貴久 助教 TODA Takahisa

  • 情報システム基盤学専攻
  • 情報システム基礎学講座
  • takahisa.toda(at)is.uec.ac.jp

はじめに ― 大規模計算の効率化

情報技術の進展により、実社会のあらゆることが記号化され、データとして蓄積・流通されるようになりました。例えば、スーパーマーケットで顧客によって購入された商品の組合せデータやセンサネットワークなどによって取得された種々の観測データがあります。このような記号データは、後に何らかの処理が施されるとき、そもそも主記憶装置におさまらないほど巨大であるとか、計算過程で莫大な数の場合分け処理を要するとか、出力が予期せず巨大になるといったことがあります。私は、これらの困難を回避(あるいは軽減)させ、計算を現実的な時間内に完遂させるための方法について研究をしています。

目標 ― 理論と実践の間のギャップを埋めること

アルゴリズム理論に携わる研究者は、計算問題を数学的に定式化し、その計算困難さを定量化したり、あるいは個々の計算法のコストを定量化したりします。これにより、解こうとしている問題が本質的な難しさをはらんでいるか否かを判定できたり、同じ問題を解く異なる方法同士の良し悪しを比較できたりするので、大変重要な研究アプローチです。一方で、理論的解析では定数倍の差が通常無視されるので、同程度のコストを持つ二つの計算法を実装して動かしてみると十倍~百倍の速度差が出ることが起こりえます。また、計算困難な問題でも、工夫すればかなり巨大な入力でも現実的な時間で解けることがありえます(制約充足問題が良い例です)。現実の問題を解きたい人にとっては、このような点は無視できないことでしょう。私の研究は、このような理論と実践の間のギャップを埋めることを目指しています。したがって、実用上の効率性にとことんこだわります。もちろん、速ければ何でも良いのではありません。提案法が設計通り動作することを証明し、その動作特性について分析します。このために理論的な解析を行うこともありますが、主に計算機実験を行うことで提案法を評価します。

特色 ― 圧縮技法

私の研究では、二分決定グラフBDDやその派生形のZDDと呼ばれる圧縮技法を用います。ここではBDDやZDDの詳細には触れませんが、ZDDは組合せデータを図1のような形式で表現したものです。この圧縮技法には二つの大きな特徴があります。第一に、巨大なデータでも圧縮することで場合によっては主記憶装置におさめることができるようになります。第二に、圧縮データを明示的に解凍することなしに、データに対する様々な操作を適用できます。実用的に用いられる多くの操作は、圧縮データサイズに依存することが知られています。現実において解くことが求められる問題には、網羅的な場合分け処理が必要とされるものが多いので、本研究のねらいは、そのような問題に対して圧縮技法を用いて組合せ爆発を抑制することです。この計算アプローチは比較的新しい研究なので、まだやるべきことがたくさん残されています。

組合せデータの二分木表現(左)とその圧縮表現ZDD(右)

図1.組合せデータの二分木表現(左)とその圧縮表現ZDD(右)

学生のみなさんへ

計算機の性能をめいっぱい使って、巨大データをオンメモリで処理することが本研究の醍醐味だと思います。問題を見つけてきて、その計算法を自分で考え、計算機を動かして実際に解く楽しみを一緒に味わいましょう。

教員紹介