メンバー
| 氏名 | 所属 | 役割 |
|---|---|---|
| 加藤 直樹 | 関西学院大学 理工学部 | 全体総括 |
| 牧野 和久 | 京都大学 数理解析研究所 | 研究メンバー |
| 伊藤 大雄 | 電気通信大学 情報理工学研究科 | 研究メンバー |
| 岡本 吉央 | 電気通信大学 情報理工学研究科 | 研究メンバー |
| 吉田 悠一 | 情報学研究所 情報学プリンシプル研究系 | 研究メンバー |
| 斎藤 寿樹 | 神戸大学 工学研究科 | 研究メンバー |
| 宇野 裕之 | 大阪府立大学 理学系研究科 | 研究メンバー |
| 瀧澤 重志 | 大阪市立大学 工学研究科 | 研究メンバー |
| 東川 雄哉 | 中央大学 理工学部 | 研究メンバー |
| Jinhui Xu | New York State University at Buffalo, Department of Computer Science and Engineering | 研究メンバー |
| 小林 祐貴 | B大学 | 研究メンバー |
| 伊藤 慈彦 | 京都大学 工学研究科 | リサーチアシスタント |
| Adnan Sljoka | 関西学院大学 理工学部 | 博士研究員 |
| 高木 尚哉 | 大阪市立大学 工学研究科 | リサーチアシスタント |
| 八田 拓郎 | 電気通信大学 情報理工学研究科 | リサーチアシスタント |
| 今田 智大 | 神戸大学 工学研究科 | リサーチアシスタント |
| 井村 実希冶 | 東京工業大学 情報理工学研究科 | リサーチアシスタント |
| 笹嶋 宗彦 | 関西学院大学 理工学部 | 受託研究員 |
研究項目：ビッグデータを対象とする劣線形時間アルゴリズムの基盤創出
本研究拠点では，ビッグデータに向けた新しい計算パラダイム，「劣線形時間アルゴリズム」パラダイムを提唱し，その理論的基礎となるアルゴリズムとデータ構造設計技術を構築し，ビッグデータ時代に向けた革新的アルゴリズム基盤として整備する．特に，様々な実問題を解く際にサブルーチンとして頻出する基礎的な探索問題，最適化問題，列挙問題に対して，確率，近似，サンプリングなどの既知の技法をビッグデータ用に深化させることにより，線形，あるいは，劣線形時間のアルゴリズム開発をおこなう．さらに，これらのアルゴリズムを最速避難計画や避難所への割り当てなどの避難計画問題，組合せ剛性理論によるたんぱく質の機能解明の研究を中心とした実問題に対し適用する．
- 線形時間アルゴリズムの開発 本研究では，組合せ最適化の問題の中で多項式時間アルゴリズムの存在が知られている基本問題に対して，確率的アプローチ，近似の概念を用いて線形時間̃ Õ(n) (=O(n polylog n)) のアルゴリズムを構築する．なかでも，最大流問題，最小費用流問題などのネットワーク問題，劣モジュラー関数最小化問題などの離散最適化問題や，剛性理論に応用のある (k，l)-疎グラフ認識問題などに焦点を当て，アルゴリズムを開発する．より実用性を高めるために，ヒューリスティックアルゴリズムの適用も含めてアルゴリズムの高速化を図る．たとえば，劣モジュラー関数最大化問題はNP困難であるが，近似比 (1-1/e) の貪欲アルゴリズムが知られており，このアルゴリズムは高速なのでビッグデータにも対応できる．一方で，劣モジュラー関数最小化問題は組合せ問題の基本問題として応用も数多くあり，多項式時間アルゴリズムが知られているが，時間計算量は O(n6) で，複雑で実装も難しく，ビッグデータに対応できない．本研究の重要な応用課題である避難計画に現れる最速避難問題が，劣モジュラー最小化問題に帰着されることもあり，劣モジュラー関数最小化問題に対する線形時間アルゴリズムの開発は，理論上，応用上重要な問題である．
- 劣線形・定数時間アルゴリズムの開発 劣線形・定数時間アルゴリズムは，データのほんの一部，すなわち o(n) あるいは定数だけの量のデータを見るだけで問題を解こうという枠組みである．特に定数時間アルゴリズムは，対象物がいかに巨大でも一定量のデータしか見ないのであるから，ビッグデータを扱うのに理想的な手法である．しかし，これまでの研究は黎明期でもあり，理論的な興味に基づくものがほとんどであったため，計算時間も定数とはいっても，定数パラメータによる指数のタワーといった非現実的なものが多く見られた．定数時間アルゴリズムの計算量が近似パラメータに対しどのような関数で表現されるかが，定数時間アルゴリズムの実用化を考える際重要であるが，系統的，網羅的な研究はこれまで行われていない．
- 漸進型アルゴリズム ビッグデータを扱うために，最初は少ないデータからおおよその性質を算出し，そして徐々にデータ量を増やしながら段々と結果の精度を上げていく，という手法が考えられる．すなわち，まず定数個のデータを読み込んで大まかな性質を計算し，次に O(log n)個，さらに O(√n) 個，といった具合にデータの量を増やしていき，時間的・資源的余裕に応じて正確な結果を得るのである．我々はこの手法を漸進型アルゴリズム (progressive algorithms) と呼び，本研究では漸進型アルゴリズムの理論基盤を構築し，その有効性を実験的に示すとともに，漸進型アルゴリズムの設計方法を開発する．
- 避難計画問題 災害発生時にできるだけ混雑を起こさないように，多くの人々をできるだけ安全な場所に早く逃がすことが避難計画における最大の目標である．現在，スマートフォンやカーナビ等の携帯端末が普及しており，情報通信技術を積極的に活用した避難誘導手法が模索・実践される動きがある．現在の方法は，携帯電話等の位置情報デバイスから最寄りの避難場所をガイドする，といったごく簡単な仕組みであり，適切な避難経路・場所の選択の問題が解消できていない．全体的に効率的な避難を達成するためには，どこにどれだけの避難者が存在するのか，さらにどの経路が安全なのかといった情報を大規模かつリアルタイムに収集・加工し，集められたビッグデータをネットワークモデルなどに置き換えて，理論的に裏付けのある方法で高速に解き，最適な避難経路や避難場所を決定する必要がある．
- 組合せ剛性理論によるタンパク質の機能解明 たんぱく質の深い理解は，生物学・医学・創薬分野において非常に重要であるが，そのためには，たんぱく質の挙動を知る必要がある．タンパク質の挙動を知るための実験は非常に大きなコストと時間がかかり，また，分子動力学に基づく計算手法は，非常に多くの計算時間を要し，実用的ではない．一方，剛性理論分野における最近の進歩により，たんぱく質の柔軟性及び挙動について，非常に高速かつ正確に挙動予測をおこなうことができ，たんぱく質挙動解析の分野に多くの進展がもたらされている．
本研究では，ビッグデータ応用という実用的視点から，定数パラメータの多項式で表現される計算時間を持つアルゴリズムを開発し，このようなアルゴリズムの可能性とその限界について明らかにしていく．具体的には，ネットワークの特性を利用した高速定数時間アルゴリズムを開発し，定数時間アルゴリズムの実用可能性を実験的に検証を行う．
本研究では，今後予想される南海地震により大きな津波被害が予想される近畿圏（大阪や和歌山など）を具体的な対象地域として選定し，避難計画で必要となるリアルタイムなデータ収集・加工の技術と理論的な避難計画モデルの開発・実装を行い，対象地域において検証を行う．具体的には，地下街避難の問題および避難所の地域への割り当ての問題，津波からの広域避難の問題に取り組む．地下街避難の問題では，時間拡大ネットワークの研究を発展させ，大規模なネットワークモデルの開発と検証を行う．避難所割り当て問題に対しては，大規模な地域を対象とした割当のための近似解法を，劣線形モデリンググループと共同で開発する．津波からの広域避難の問題では，南海トラフ地震による大阪湾沿岸地域への津波浸水の高精度なシミュレーションを行う．そして，そのデータを使って，時間と共に通行可能な箇所が変化する時間拡大ネットワークを構築し，構築された大規模な時間拡大ネットワークを効率的に解くために，本プロジェクトで開発する最大流問題の改良型アルゴリズム等を実装し，検証を行う．
本研究は，本グループで開発する劣線形時間アルゴリズムを基礎に，既存のアルゴリズムの改善をおこない，劣線形データ構造グループと連携しながら，巨大スケールのたんぱく質の挙動を明らかにする手法の開発をおこなう．具体的には，剛性理論の手法を用いることにより，従来捉えることが困難であった，たんぱく質アロステリ，GPCRの挙動解明を中心に焦点を当てて，たんぱく質の挙動と機能の関係性を調査する．