支持度が \(s\) であるようなシンボルを，支持度に対する許容誤差が \(\epsilon\) を保証しつつ，データストリームから列挙するアルゴリズム．
- 最初は \(\mathcal{D}\) は空．この集合の要素は \((e,f,\Delta)\)．ただし，\(e\) はシンボル，\(f\) はシンボルの数，\(\Delta\) は最大許容誤差．
- 現在読んだストリームのシンボル数は \(N\)，バケット幅 \(w=\lceil 1/\epsilon\rceil\)，そして現在のバケットは \(b_{current}\) 番目．
- 新たなシンボル \(e\) が来たら
- バケット内のシンボルが \(\mathcal{D}\) 中にある場合には，そのエントリーの \(f\) を一つ増やし，\(\Delta\) を \(b_{current}-1\) とする．
- バケット内のシンボルが \(\mathcal{D}\) 中にない場合には，新たなエントリ \((e,1,b_{current}-1)\) を作る．
- バケットを読み終わったら，\(f+\Delta\le b_{current}\) のエントリーを削除する．
- 利用者の要求に応じて，支持度が \(s\) 以上のシンボルを取り出すには，\(f\ge(s-\epsilon)N\) を満たすシンボルを \(\mathcal{D}\) から取り出す．
-- しましま
関連項目†
リンク集†
関連文献†
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
