SCARAB: Scaling Reachability Computation on Large Graphs (SIGMOD'12)
到達可能性クエリ．
背景
- 既存研究
- transitive closure: index size がダメだ！
- labeling: index time がダメだ！
- online: query time がダメだ！
組み合わせて安定した性能のアルゴリズムを作る！
アルゴリズム
- バックボーンの構築：代表点を選ぶ，グラフ全体のスケッチ
- バックボーンへのアクセス：最寄りのバックボーン
- バックボーン上で到達可能性クエリをする
バックボーンを用いたクエリ
- 距離 ε で行けない頂点に行くためには，距離 ε で行ける backbone を通って行けるようにする
- backbone について既存の到達可能性クエリの手法を適用
- 距離ε以下のバックボーン頂点集合を前計算しておいて，クエリ発行しまくってクエリに答える．
- 枝狩り：頂点集合を減らす（行ける物同士を両方入れておく必要なし），枝狩り，online search 系なら
バックボーンの構築
最小を求めるには，set cover になるので NP-hard．適当な貪欲法により求める．
実験結果
微妙
