Lossy Countingアルゴリズムはどのようにして頻繁なアイテムを見つけますか？

ユーザーは、最小サポートしきい値σと、εとして示されている以前にバインドされたエラーを含む2つの入力パラメーターをサポートします。着信ストリームは、理論的には幅w =[1/ε]のバケットに分割されます。

Nを現在のストリームの長さ、つまりこれまでに表示されたアイテムの数とします。アルゴリズムには、頻度が0より高いすべての要素の頻度リストデータ構造が必要です。すべての項目について、リストはf、おおよその頻度カウント、および∆、fの可能な最大誤差をサポートします。

アイテムのアルゴリズムプロシージャバケットは次のとおりです。新しいバケットが到着すると、バケット内のアイテムが頻度リストに挿入されます。特定のアイテムがリストに存在する場合、その頻度カウントfを単純に増やすことができます。それ以外の場合は、頻度カウント1でリストに追加できます。新しいアイテムがb番目のバケットからのものである場合、アイテムの頻度カウントで発生する可能性のある最大のバグである∆をb-1に設定できます。

バケット境界が取得されるたびに（つまり、Nが幅wの倍数に達した場合（w、2w、3wなどを含む））、頻度リストが決定されます。 bを現在のバケット番号とします。アイテムエントリが、そのエントリに対してf + ∆≤bの場合、削除されます。このアプローチでは、アルゴリズムの目的は、頻度リストを小さく維持して、プライマリメモリに収まるようにすることです。各アイテムに保存される頻度カウントは、アイテムの実際の頻度または最小化されます。

近似アルゴリズムの重要な要素は、近似比（または誤差限界）です。アイテムが削除された場合を見てみましょう。これは、アイテムのf + ∆≤bの場合に表示されます。ここで、bは現在のバケット番号です。

b≤N/w、つまりb≤εNであることがわかります。アイテムの実際の頻度は最大でf+Δです。したがって、最小化できる項目はεNです。このアイテムの実際のサポートがσ（これは頻繁に扱われる最小のサポートまたは下限）である場合、実際の頻度はσNであり、頻度リストの頻度fは最小である必要があります（σN-εN 。

したがって、f値が最小（σN-εN）の頻度リスト内のすべての項目を出力すると、いくつかの頻繁な項目が出力されます。さらに、いくつかの頻度の低い項目（実際の頻度が最小σN-εNであるがσN未満）が出力されます。