劣線形データ構造グループ

ビッグデータを対象とする劣線形データ構造の基盤創出

近年の多くのビッグデータにおいて，ムーアの法則をはるかに凌駕する勢いでデータ量が増加しているが，このようなデータに対して解析等を行うことが今現在 できていたとしても，それが線形時間アルゴリズムであったり，線形サイズのデータ構造を必要とするものであったりすると，早晩その解析が破綻することは明 らかである．これに対し，劣線形時間あるいは劣線形スペースでデータを処理することが可能なデータ構造，すなわち劣線形データ構造の開発やそのためのパラ ダイムを構築することができれば，そのような破綻を回避できる可能性がある．そこで，本グループは，ビッグデータの検索や解析の効率化・高精度化のための 新しい劣線形データ構造の開発を行う．
ビッグデータは，単純なランダムなデータの集積ではなく，通常は何らかの目的をもって集められたデータである．このことは，ビッグデータの情報量が実は見 かけほど大きくはない可能性があることを意味する．そのような「実は」情報量の少ない「ビッグデータ」は，うまく効率的に処理できる劣線形データ構造を持 つ可能性は高いと思われる．そこで本グループでは，以下にあげる３つの異なるアプローチを用いて劣線形データ構造研究を行い，現実のビッグデータ解析・検 索へつなげていくことをめざす．

情報論的アプローチによる劣線形データ構造の開発

１つ目のアプローチでは，ビッグデータの実際の情報科学的な情報量に着目し，データをもとのサイズよりも小さく，できれば劣線形サイズで保持しながら解 析，検索を行う技術を開発する．ビッグデータが圧縮できている場合に，その情報を圧縮して保持したまま解析することができれば，データ量Nに関する時間で はなく，その圧縮したデータ量すなわち情報量Hに関する計算時間で計算できる可能性がある．また，データの格納領域が小さいまま計算できれば，I/O計算 量や並列化時の通信計算量，あるいはメモリの小さいGPGPUにおける実計算量なども減らすことができる可能性がある．さらに，一般的には情報量に対して 劣線形サイズの厳密索引は情報論的に不可能であるが，現実のビッグデータにおいては，情報量の定義を巨大データに対して正確に定義することが難しく，現実 のデータと情報量の定義に乖離があるような場合が考えられる．また，必ずしも厳密な索引を要しない場合も考えられる．そういった場合には，この情報論的不 可能性は打破できる可能性がある．このアプローチでは，文字列等の基礎的データ構造に対し，圧縮したままのデータ検索・解析を行う新しい情報科学パラダイ ムの創出をめざす．

列挙論的アプローチによる劣線形データ構造の開発

２つ目のアプローチでは，列挙アルゴリズムがきわめて少ない情報量からビッグデータに匹敵する巨大データを生成することができることに注目し，そのような 巨大データに対する劣線形データ構造の研究を行う．このように生成された巨大データに対して解析を行う場合，解1つあたり定数時間で計算できるようなアル ゴリズム，すなわち列挙データ数に関して線形時間のアルゴリズムは効率的であるとはいえない．列挙データにおいては，そのデータの生成規則はわかっている ため，それを活用した効率的アルゴリズムを考えることが，これまでも行われてきている．しかし，そのようなきれいなモデルに基づいて生成された「均一な」 データでは効率的なアルゴリズムが存在しても，その均一性が破れると効率的ではなくなってしまうことが多い．このように現実のビッグデータがきれいなモデ ルからの生成データであるということはほとんどないため，均一性が多少破れているデータに対しても効率的な解析が行えるような柔軟なデータ構造が要求され る． このアプローチでは，このような列挙アルゴリズムの観点から，不均一列挙データに対する検索や索引のための劣線形アルゴリズムを列挙理論の観点からパラダ イム創出をめざす．

実応用アプローチによる劣線形データ構造の開発

３つ目のアプローチでは，情報科学的な一般的な枠組みだけでなく，実際の現実のデータが持つ様々な実際の性質も活用したより具体的な劣線形データ構造の開 発を行い，それによって，実際の解析や検索を効率よく行うことをめざす．さらに，そのような具体的応用研究を通じて，これまでの情報科学理論で捉えられな かった新しいデータ構造研究のパラダイムを構築することもめざす．現実のデータとしては，タンパク質立体構造データ，次世代シークエンサーデータ，店舗の POS・センサーデータなどの経営データ等を対象とする．このアプローチでは，これらの多岐にわたる具体的研究を通じてそれらに共通するデータ構造パラダ イムの創出も狙っていく．

メンバー