最適化問題に対する超高速&安定計算

大規模最適化問題、グラフ探索、機械学習やデジタルツインなどの研究のお話が中心

グラフ探索と応用

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

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

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

コメント    この記事についてブログを書く
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする
« SDPA(SDPARA)のボトルネック ... | トップ | 全米道路ネットワークに対す... »
最新の画像もっと見る

コメントを投稿

ブログ作成者から承認されるまでコメントは反映されません。

Weblog」カテゴリの最新記事