Piggybacking on Social Networks - todo314 @ ウィキ

Piggybacking on Social Networks

• Aristides Gionis, Flavio Junqueira, Vincent Leroy, Marco Serafini, Ingmar Weber
• In VLDB 2013

• 岩田さん

• Piggybacking?
  • おんぶ

概要

• 巨大なSNS
• クラスタ係数を利用してスループット向上
• ↑最適化問題
• アルゴリズム
  • O(log n)近似
  • Hadoop用のヒューリスティクス

スループット

• とりあえず1ユーザに1台のサーバ
  • 実際は1台が複数ユーザ

定式化

• Social Dissemination Problem
• 辺 u→v: vがuをフォロー
• クエリ
  • Produce: 情報発信
    • コスト r_p(u)
  • Consume: フォローイングの最新情報を得る
    • コスト r_c(u)
• スケジュール
  • Push edges
    • uv ∈ H: uがproduceしたらサーバvに保存
  • Pull edges
    • uv ∈ H: vがconsume したらサーバuから情報を得る
• スコア
  • c(H,L)=Σr_p(u)+Σr_c(v)
• Push, Pullを上手く使うと、コストを減らせる
  • Piggybackingによるz被覆になる

近似アルゴリズム (ChitChat)

• NP-hard
• 集合被覆のO(log n)近似アルゴリズム
• 辺の選び方
  • ハブごとにばらしても問題ない
• ハブ固定したら、DensestSubgraph、多項式時間
  • 2近似を使って早くする

ヒューリスティクス (ParallelNosy)

1. 効率よさそうな部分集合を並列に探す
2. 並列にconflictを解消
3. ↑を繰り返す

Incremental updates

• 定期的に最適化し直す

実験

設定

データセット

• Flickr, Twitter
  • でかい

コスト関数

• それっぽく

マシン環境

• Hadoop cluster (1500 cores)

目的関数値

• ベースラインに比べて半分
• イテレーション1hour

実際のスループット

• サーバ台数が増えると、ちょっと良くなる、1.3倍

ParallelNosy vs ChiChat

• ヒューリスティクス(´・ω・｀)ｼｮﾎﾞｰﾝ

VLDB system performance

2013-10-17 23:41:24 (Thu)