Fast Fully Dynamic Landmark-based Estimation of Shortest Path Distances in Very Large Graphs

Konstantin Tretyakov, Abel Armas-Cervantes, Luciano García-Bañuelos, Jaak Vilo, and Marlon Dumas. 2011. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. In Proceedings of the 20th ACM international conference on Information and knowledge management (CIKM '11), Bettina Berendt, Arjen de Vries, Wenfei Fan, Craig Macdonald, Iadh Ounis, and Ian Ruthven (Eds.). ACM, New York, NY, USA, 1785-1794. DOI=10.1145/2063576.2063834 http://doi.acm.org/10.1145/2063576.2063834

静的ばかり議論されてきた最短路クエリがついに＆いきなり高性能に動的になった (バグあり)

内容

  • 問題
    • SPQ on complex networks
    • on memory
    • 更新も考えちゃうかも!
  • アプローチ
    • landmark-based (普通)
    • テクニック
      • LCA, shortcutting, landmarks-bfs
      • この辺は，path-sketch の論文で扱われていたので新規性はないがあれは on disk で実験してたり
  • アップデート
    • 最短路木の更新って割とできるじゃん
    • そんな簡単にできるわけないだろ!!!!!!!!!!いい加減にしろ!!!!!!!!!!!!!
  • 実験
    • 最大のグラフが圧巻の大きさ: Skype V=454M / E=3.1B
    • このデータセットは public じゃないと思うんだが…欲しい…
  • 結果はまぁ結構いい