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
  • Hadoop のあやしいヒューリスティクス
• 実験
  • 10000 core とか使っていて派手