gSketch: On Query Estimation in Graph Streams - todo314 @ ウィキ

gSketch: On Query Estimation in Graph Streams

• Peixiang Zhao, Charu C. Aggarwal, Min Wang
• VLDB 2012

• yanoさん

概要

• ストリームモデルでのグラフの扱い

問題

• 辺がストリームでもらえる
  • (xi, yi; ti)の形、tiはタイムスタンプ
  • f(xi, yi; ti): 重みのようなもの、普段は1
• 全体構造は謎
• クエリ
  • Edge Query
    • Σf(x,y,ti)を推定
    • ある辺が今までに来た回数
  • Aggregate Subgraph Query
    • あるサブグラフに含まれる辺が来た回数の平均・合計・最小を求める
    • Γ(f~(x1, y1), …, f~(xk, yk))を推定
    • Edge Queryと大差ない

Global Sketch

• 頻度推定の手法を適用、よくあるやつ
• CountMin Sketch
  • d*w配列
  • [1,w]の値をとる(h1,…,hd)d個のハッシュ関数
• 誤差評価
  • N個見た段階で
  • 1-e^d以上の確率でf<=f~<=f+e*N/w
• やばいのでSketchを分割して頑張る

提案手法 gSketch

• 分割の仕方を工夫？？？

実験

• Global Sketchよりはイイ感じ？

VLDB streaming algorithm

2013-11-05 23:43:25 (Tue)