Efficient Ad-hoc Search for Personalized PageRank (SIGMOD'13)

  • 問題
    • PPR の top-k を前処理なしで高速に求める
    • similarity は求めない,top-k の順序を exact に求める
  • 提案手法 (Castanet)
    • 4.2 Similarity estimation
      • 長さ i の RW (jump なし) での分布 R_i[u] から lower bound と upper bound が得られる
    • 4.3 Subgraph-based search
      • L_i := k-th highest な lower bound 以上の upper bound を持っている頂点集合
      • S_i := L_i - もうランクが完全にわかった奴
      • それらの bound を知るために,それらの R_i[u] が知りたい
      • それらの R_i[u] を知るために,「S_i とそれに reachable な頂点集合であって始点から距離 i 以下」というのがサブグラフ
      • 始点からの BFS を予め行なっておけば,incremental に subgraph を継ぎ足していける
  • 実験結果
      • l:L_i の平均サイズ
      • n,m:サブグラフの頂点数辺数
      • t:イテレーション
      • T: the original iterative approach って書いてあるけどどこまで収束させた場合だろう?
      • query nodes の数は 3.コレを動かした実験はしてない.
    • 見た感じ
      • subgraph のサイズはだいたい 10% ぐらいというところ
      • reachable なところも全部保持しないといけないというのが厳しい
      • かなあと思ったけど L_i の平均サイズも結構大きかった

前処理なしで exact で高速でパラメータもなしってもうメリットしか無いわけで,とてもすごい