大規模グラフアルゴリズムの最先端

昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります．

大規模グラフアルゴリズムの最先端
View more presentations from iwiwi

当日は Ustream もされており，録画された発表もご覧になれます．

内容の流れとしては，以下のようになっています．

  • 導入
  • アルゴリズム界隈での話題
    • 最新の研究動向
    • 道路ネットワークでの最短路クエリ処理
      • 基礎的な手法：双方向 Dijkstra，A*, ALT
      • 最新の手法：Highway Dimension + Hub-Labeling Algorithm
  • DB 界隈での話題
    • 最新の研究動向
    • 複雑ネットワークでの最短路クエリ処理
      • 基礎的な手法：ランドマークを用いた最短距離推定
      • 最新の手法：Core-Fringe 構造の木分解による活用
  • HPC 界隈での話題
    • 最新の研究動向，Graph500
    • SMP マシンでの並列 BFS
    • クラスタでの分散 BFS：1D/2D 分割法

交通ネットワーク・ソーシャルネットワーク・Web グラフなどの大規模なグラフを処理するプラクティカルなアルゴリズムに関心があるアカデミックコミュニティとして，アルゴリズム界隈，DB 界隈，HPC 界隈を取り上げ，それぞれでの話題について触れています．最初に全体的な研究動向に触れ，特に 1 つのトピックとして最短路に関連した問題を紹介し，定番となっている手法と最新の手法について触れています．特に，最新の手法としたものは全て 2010 年以降のものとなっているので，結構ホットかもしれません．