SCARAB: Scaling Reachability Computation on Large Graphs (SIGMOD'12)

到達可能性クエリ.

背景

  • 既存研究
    • transitive closure: index size がダメだ!
    • labeling: index time がダメだ!
    • online: query time がダメだ!

組み合わせて安定した性能のアルゴリズムを作る!

アルゴリズム

  1. バックボーンの構築:代表点を選ぶ,グラフ全体のスケッチ
  2. バックボーンへのアクセス:最寄りのバックボーン
  3. バックボーン上で到達可能性クエリをする
バックボーンを用いたクエリ
  • 距離 ε で行けない頂点に行くためには,距離 ε で行ける backbone を通って行けるようにする
  • backbone について既存の到達可能性クエリの手法を適用
  • 距離ε以下のバックボーン頂点集合を前計算しておいて,クエリ発行しまくってクエリに答える.
  • 枝狩り:頂点集合を減らす(行ける物同士を両方入れておく必要なし),枝狩り,online search 系なら
バックボーンの構築

最小を求めるには,set cover になるので NP-hard.適当な貪欲法により求める.

実験結果

微妙