読者です 読者をやめる 読者になる 読者になる

Piggybacking on Social Networks (VLDB'13)

  • ツイッターみたいな購読ベースの SNS サービス
  • 問題
    • 有向グラフ=購読関係,u->v := uの情報をvが購読
    • クエリ:Produce (発信),Consume (最新情報取得)
    • push edge と pull edge を決めておく
      • push edge: 始点で produce が起きた瞬間,新データを全部伝搬
      • pull edge: 終点で consume が起きた瞬間,新データを全部伝搬
  • 現象 Piggybacking
    • u->w が push,w->v が pull なら,u->v が w をハブする piggybacking
      • u->v は push でも pull でも通信しなくてよい!
  • 近似アルゴリズム ChitChat
    • 集合被覆ベース,O(log n) 近似
      • Densest Subgraph に帰着
      • でも厳密にとくと遅いので 2 近似アルゴリズムを使う:次数/重みが最小の頂点を順に除去
  • ヒューリスティクス ParallelNosy
  • 実験
    • 10000 core とか使っていて派手