lossy countingアルゴリズム (lossy counting algorithm)

支持度が \(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}\) から取り出す.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-11-09 (火) 23:12:14 (2217d)