簡潔データ構造の理論と応用
【研究分野】情報学基礎理論
【研究キーワード】
簡潔データ構造 / ビッグデータ / データ構造 / データ圧縮 / 並列アルゴリズム
【研究成果の概要】
理論的にも実用的にも優れた簡潔データ構造を複数開発した．例えば，集合族を表現するZDDの使用メモリを削減し，高速に演算を行える手法を開発した．実験により，頻出アイテム集合を求める問題において，通常のZDDと比較して使用メモリが 1/3 になり，実行時間の増加は40% のみであった．
また，高次元直交領域探索のための省メモリのデータ構造を開発した．
【研究の社会的意義】
ビッグデータ処理で問題になるのはデータが大量にあるため計算機のメモリ上での処理が行えないということである．古典的な手法ではデータをハードディスク上に格納して処理を行うI/Oアルゴリズムを用いていた．しかしハードディスクのランダムアクセスはメモリへのアクセスとは比べ物にならないほど低速であり，ビッグデータ処理には時間がかかっていた．
簡潔データ構造では，データ構造のサイズはo(n)，つまりデータ量の劣線形となっており，データを計算機のメモリ上に格納することができ，スケーラブルなアルゴリズムが開発できる．
【研究代表者】
【研究種目】基盤研究(B)
【研究期間】2016-04-01 - 2021-03-31
【配分額】7,280千円 (直接経費: 5,600千円、間接経費: 1,680千円)