グラフ探索と応用

大規模なネットワークデータ上における最短路計算などのグラフ探索アルゴリズムには以下のように非常に幅広い応用があることが知られている。

1. 交通ネットワークにおける経路検索(カーナビゲーションシステム等)
2. 災害時における避難や誘導等の支援システム
3. Twitter, Facebook などのソーシャルネットワークデータの解析

これらの応用においては、今後は超大規模ネットワークデータ（点数１億以上) が対象となることが予想されるので、超高速な探索アルゴリズムとソフトウェアの開発が急務となっている。例えば上記のソーシャルネットワークデータの解析においては、ネットワーク内での各点の重要度を計算することによって、各点の周辺、及び広域内における影響（情報の伝播力) を推定することができる。しかし、そのためには大規模ネットワークデータ上での短時間に大量のグラフ探索を行う必要があり、メモリ要求量を抑えた上で、大量のスレッドを生成、同時並行的にグラフ探索を行うことによって、極めて高いスループットを得ることができる。