損失カウントアルゴリズム

損失カウントアルゴリズムは、データストリーム内の要素のうち、出現頻度がユーザー指定の閾値を超える要素を識別するアルゴリズムです。このアルゴリズムは、データストリームを頻繁に出現する要素ごとにバケットに分割しますが、メインメモリには可能な限り多くのバケットを一度に書き込みます。このアルゴリズムで計算される頻度は必ずしも正確ではありませんが、ユーザーが指定できる誤差閾値が存在します。アルゴリズムの実行時間とメモリ使用量は、指定された誤差閾値に反比例します。つまり、誤差が大きいほど、フットプリントは小さくなります。

このアルゴリズムは、コンピュータ科学者のラジーブ・モトワニ氏とグルミート・シン・マンク氏によって開発されました。ネットワークトラフィック測定、ウェブサーバーログ、クリックストリームなど、データが有限のデータセットではなく連続的なデータストリームの形式をとる計算処理に応用されています。

一般的なアルゴリズムは以下のとおりです^{[ 1 ]}

• ステップ 1:受信データ ストリームを幅のバケットに分割します${\displaystyle w=1/\epsilon }$、 どこ${\displaystyle \epsilon }$ユーザーがエラー境界として言及している（最小サポートしきい値 =${\displaystyle \sigma }$)
• ステップ2：新しいバケット値に従って、各項目の出現頻度カウントを増やします。各バケットの後に、すべてのカウンターを1減らします。
• ステップ 3:繰り返し – カウンターを更新し、各バケットの後にすべてのカウンターを 1 減らします。