研究の概要
今世紀に入り注目を浴びているビッグデータは，そのデータ量の膨大さ故に，その基礎となるアルゴリズム理論に根本的な変革が迫られている．例えば，これまでは多項式時間アルゴリズムならば「速い」アルゴリズムであると考えられてきたが，ペタスケールやそれ以上のビッグデータに対して O(n2) 時間アルゴリズムを直接適用するだけでは，計算資源や実行時間などの点で大きな困難に直面する．少なくとも線形時間，場合によっては劣線形時間や定数時間アルゴリズムが求められている．本研究では，その変革を支える劣線形時間パラダイムを提唱し，ビッグデータ用のアルゴリズムとデータ構造，およびモデリング技法を開発し，ビッグデータ時代に向けた革新的アルゴリズム基盤を構築する．