Document

Best
Paper
研究紹介#1
FINDING FREQUENT ITEMS IN DATA
STREAMS
GRAHAM CORMODE (AT&T LABS, USA), MARIOS HADJIELEFTHERIOU (AT&T LABS, USA).
1
The Frequent Items Problem?
• • Itemのストリームにおいて、与えられた閾値より
たくさん目の前を通り過ぎたネタは何か？
も多く出現するItemを全て見つける
• 例：
– ItemがTCPパケットなら、Frequent Itemsは
• 人気のある終端
• バンド幅を占有しているユーザ
– Itemがサーチエンジンクエリなら、Frequent Itemsは
• 人気のある検索語
2
定義
• Stream S of n items: t1, …, tn.
t1 t2 t3 t4 t 5 t6 t7 t8 t9
・・・
tn
• Frequency of item i is fi = |{j|tj = i}|.
ti1 A
t2 tZ3 ti4 tZ5 A
t6 tP7 ti8 ti9 tZ10 → fi =4
• The exact φ-frequent set is: {i|fi > φn}.
i A Z
i
φ：ストリーム中に出現する頻度を表す変数
Z A P i
i
Z
n=10
– もし φ=0.2 なら Frequent Set = {i|fi > 2}
– よって、0.2-Frequent Items = i Z
3
定義(続き)
• 実際にこの論文が扱うのは…
– ε-approximate frequent item要件
• 結果集合Fの全てのiにおいてfi>(φ-ε)nが成り立ち、
• fi>φnの成り立つ{i|i∉F}は無い
– 簡単に言うなら
• 間違い(False Positive)は含んでるかもしれないけど
• 見落とし(False Negative)は無い
i A Z
優
Z
i
i
良
Z A P i
i A Z
False Positive
i
Z
不可
φ=0.2 (=3回以上出現)
Z A P i
False Nagative
4
Frequent Item Problem
• 要件
– 速い動作
– 少ない作業領域
– 正確さ
• アルゴリズムの分類
– Counter Based
– Quantile Based
– Skeches
5
本研究では・・・
• 可能なアルゴリズム全て実装
• 一般的なテストベッド上に構築
• 可能な限り様々な実装方式を採用
– 様々なデータ形式
– 様々なアルゴリズム・デザイン
• 様々なシナリオで何がBestかを調べる
6
① Counter Based Algorithms
• 特徴
– Fast
– Small Space
– Deterministic
– Do not Support Deletions
• 削除のイベント(item)を含むストリームは対象外
7
Majority Algorithm (Boyer)
準備：
• 最も頻出なアイテムを探すアルゴリズム
ストリーム
カウンタ値・保存アイテム
赤赤緑緑緑紫
1 2 1 0 1 0
緑がMajority!
– カウンターを1として最初のアイテムを保存する
– 次に同じアイテムが来たらカウンターを1増やす
– 違うアイテムが来たら…
• もしカウンターが0でなければ → カウンターを1減らす
• カウンターが0ならば → カウンターを1として新しいアイテムを保存
– 最後に保存されていたアイテムがMajority！
ただし、本研究で扱うのはTop-kを得るアルゴリズム
8
#1:Frequent
Algorithm
赤赤青緑緑
• 出典
– E. Demaine, A. L´opez-Ortiz, and J. I. Munro.
Frequency estimation of internet packet streams with limited space.
In European Symposium on Algorithms (ESA), 2002.
– R. Karp, C. Papadimitriou, and S. Shenker.
A simple algorithm for finding frequent elements in sets and bags.
ACM Transactions on Database Systems, 28:51–55, 2003.
e.g. Frequent(k=2)
T=
∅
2 1
1
0
A. 赤緑
赤i ∊ T ?
青
緑
Yes!
No!
|T|<k
No!
Yes!
カウンタを1増やす
アイテムをカウンタと
ともにTへ保存
カウンタ0のアイテム
はTから削除
Tの全てのアイテム
のカウンタを1減らす
9
#2:Lossy
Counting
赤赤青緑緑赤
• 出典
– G. Manku and R. Motwani.
Approximate frequency counts over data streams.
In International Conference on Very LargeData Bases, 2002.
e.g. LossyCounting(k=2)
n++
赤
青∊T?
緑
No!
カウンタ値を⊿+1とし
Tに保存
カウンタを1増やす
Yes!
5
6
1
3
4
2
2
3
0
1
22 
 
n
 k    ?
home
No!
Yes!
n
 
k 
全てのj∊Tに関して
T=
∅
1 3
2
3
2 2
⊿= 0321
A. 赤緑
カウンタが⊿未満ならT
からアイテムを削除
n= 5206431
home
10
#3:Space
Saving
赤赤青緑緑
• 出典
– A. Metwally, D. Agrawal, and A. E. Abbadi.
Efficient computation of frequent and top-k elements in data streams.
In International Conference on Database Theory, 2005.
e.g. SpaceSaving(k=2)
??
i赤
∊T
緑∊ T
青
Yes!Yes!
T=T= ∅
2
1
No!No!
|T|<k
??
|T|<k
カウンタを1増やす
カウンタを1増やす
Yes!Yes!
No!No!
最少カウンタ値に
最少カウンタ値に
1を加えた値を得る
1を加えた値⇒
2
アイテムをカウンタと
アイテムをカウンタと
ともにTへ保存
ともにTへ保存
31
A. 赤緑
新しいアイテムカウンタ値で
新しいアイテムカウンタ値で
最小カウンタアイテムを置換
最小カウンタアイテムを置換
11
実験
• VC++, g++
• データセット
– Zipfデータ
– AT&T UDP and TCP backbone traffic
• 計測
– 速度
– スペースコスト
– Recall, Precision
– Average Relative Error(ARE):相対誤差の平均値
12
実装系
3つのアルゴリズム、計5種類の実装系で計測
• F: Frequentアルゴリズム
• LC: Lossy Counting アルゴリズム(⊿なし)
• LCD: Lossy Countingアルゴリズム
• SSL: Space Savingアルゴリズム(Linked List実装)
• SSH: Space Savingアルゴリズム(Heap実装)
13
結果(Speed)
正誤表:
1. グラフの縦軸の速・遅が逆
2. オレンジ色の線の位置
3. その他、下線部を更新
スピード
Log Scale
F: Frequentアルゴリズム
LC: Lossy Counting アルゴリズム(⊿なし)
LCD: Lossy Countingアルゴリズム
SSL: Space Savingアルゴリズム(Linked List実装)
SSH: Space Savingアルゴリズム(Heap実装)
•FとSSLが速い
•Linkd List は総じて速い
•Heapは低skew時に遅い
•φの影響は殆ど無い
14
結果(Size)
スピード
サイズ
F: Frequentアルゴリズム
LC: Lossy Counting アルゴリズム(⊿なし)
LCD: Lossy Countingアルゴリズム
SSL: Space Savingアルゴリズム(Linked List実装)
SSH: Space Savingアルゴリズム(Heap実装)
•SpaceSavingに関して
•Heapは小さい
•Linked Listはφが低い
時Heapの二倍
15
結果(Recall)
再現率
Log Scale
F: Frequentアルゴリズム
LC: Lossy Counting アルゴリズム(⊿なし)
LCD: Lossy Countingアルゴリズム
SSL: Space Savingアルゴリズム(Linked List実装)
SSH: Space Savingアルゴリズム(Heap実装)
•Recallはすべて100%
=false negative無し
16
結果(Precision)
適合率
Log Scale
F: Frequentアルゴリズム
LC: Lossy Counting アルゴリズム(⊿なし)
LCD: Lossy Countingアルゴリズム
SSL: Space Savingアルゴリズム(Linked List実装)
SSH: Space Savingアルゴリズム(Heap実装)
•Fは適合率が低い
•LC, LCDはskewの影響
•SSL, SSHはほぼ100%
•データセットの影響無し 17
結果(Average Relative Error)
ARE
Log Scale
F: Frequentアルゴリズム
LC: Lossy Counting アルゴリズム(⊿なし)
LCD: Lossy Countingアルゴリズム
SSL: Space Savingアルゴリズム(Linked List実装)
SSH: Space Savingアルゴリズム(Heap実装)
•Fのみ誤差がある
•低skew時に顕著
•HTTP, UDPは異なる特徴
(データセットによる違い) 18
まとめ
• 勝者： Space Savingアルゴリズム
– 特にHeap実装
• 消費スペースが小さい
• Recall, Precision = 100%
• Lossy CountingやFrequentに比べて速い
– Linked List実装
• スピードだけでいえば最速
• ただしHeapに比べて二倍の消費スペース
– スペースが問題とならない場合はLinked Listが良いだろう…
19
と、ここまでで
• 論文の1/3です・・・
• Frequent Item Problem
– Counter-base algorithm
ここでは(VLDB08でも)、
– Quantile algorithm
これらに関してはサマリー
– Sketch algorithm
• こんなに残っています。
20
② Quantile Algorithm
• Greenwald and Khanna (GK)
• Quantile Digest (Suri et al.)
• 特徴
– Large space
– Answer a more general problem
• まとめ
–
–
–
–
総じてQDはGKに勝っている
スピードは遅い
メモリ効率も悪い
Frequencies Accuratelyの見積もりができない
21
③ Sketch Algorithm
• CountSketch (Charikar et al.)
• CountMin Sketch (Cormode and Muthukrishnan)
• 特徴
– 削除に対応
• まとめ
– どちらが勝っているかは結果からは分からなかった
– Hierarchical CountMin はスピードが速く、メモリ効率も良かった。
• ただしskewなデータでのみ正確だった
– Combinatorial Group Testing CountMinは早く正確だった。
• ただしメモリ効率は悪かった
– CountSketchはメモリ効率が良く正確だった。
• ただしスピードが遅い
22
おわりに
• ここで紹介したアルゴリズムの実装は全て
以下のURLで公開されている。
– http://research.att.com/~marioh/frequentitems/index.html
23

Download Report