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 で高速でパラメータもなしってもうメリットしか無いわけで，とてもすごい