gSketch: On Query Estimation in Graph Streams
-
Peixiang Zhao, Charu C. Aggarwal, Min Wang
-
VLDB 2012
概要
問題
-
辺がストリームでもらえる
-
(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
実験
VLDB streaming algorithm
2013-11-05 23:43:25 (Tue)
最終更新:2013年11月05日 23:43