K-Reach: Who is in Your Small World
"K-Reach: Who is In Your Small World" by James Cheng, Zechao Shang, Hong Cheng, Haixun Wang, Jeffrey Xu Yu. VLDB 2012.
- 問題
- 距離 k 以下で到達可能か答える
- 構築アルゴリズム
- 頂点被覆 S を求める（近似）
- k-reach というインデックスを作る
- k-reach とは重み付き有向グラフである
- 頂点集合は S，辺集合は k 以下で行ける頂点対，重みは距離に応じて k-2, k-1, k
- (これつくるために全始点から BFS するらしい…ｗｗｗ)
- クエリアルゴリズム
- 自明（近傍みるだけ）
- 実験結果
- 実験してるのは数万頂点・数万辺のグラフ
- せいぜい数百ミリ秒で構築終わるらしい
- はやすぎだろ，もっとデカイので実験してよ
- これはもしや，オーダーが悪くてデカイのだと既存手法に大きな差が出てしまうから，このサイズにしてるのでは？
- クエリ 5ns ってちょっと…？？
論文はよく書かれていると思った，流石 James Cheng だなあ．
木分解を用いた最短経路クエリを，「無向専用だから今回は使えない」と言っているが全くそんなことはない．現にその著者は到達可能性クエリに同じアルゴリズムを使った論文も一応出してる．適当だなぁ．
