近似計数アルゴリズム

近似計数アルゴリズムは、少量のメモリを使用して多数のイベントを計数することを可能にします。1977 年にベル研究所のロバート・モリスによって発明されたこのアルゴリズムは、確率的手法を使用してカウンタをインクリメントします。1980 年代初頭にINRIAロッケンクールのフィリップ・フラジョレによって完全に分析され、近似計数という名前が付けられ、研究コミュニティでの認知に大きく貢献しました。ネルソンとユーは、近似の高品質と失敗の確率の低さに焦点を当てると、モリスカウンタへのごくわずかな変更が、この問題に対するすべてのアルゴリズムの中で漸近的に最適であることを示しました。 ^{[ 1 ]}このアルゴリズムはストリーミングアルゴリズムの先駆けの 1 つと考えられており、データ ストリームの周波数モーメントを決定するというより一般的な問題がこの分野の中心となっています。

モリスアルゴリズムを用いると、カウンターは実際のカウントの「桁違いの推定値」を表す。この近似値は数学的に偏りがない。

カウンタをインクリメントするには、擬似乱数イベントが使用され、インクリメントは確率的なイベントとなります。スペースを節約するため、指数のみを保持します。たとえば、2進数では、カウンタはカウントを1、2、4、8、16、32、および2のすべてのべき乗と推定できます。必要なメモリは、指数を保持するだけです。

例えば、4から8に増やす場合、カウンターが増加する確率が0.25となるような擬似乱数が生成されます。そうでない場合は、カウンターは4のままです。

以下の表は、カウンターの取りうる値の例を示しています。

カウンターが101の値を保持している場合、これは指数5（101の10進数表記）に相当し、推定カウントは$25$、または 32。実際の増加イベントのカウントが 5 であった確率はかなり低い ($\displaystyle {\frac {1}{1024}}=1\times {\frac {1}{2}}\times {\frac {1}{4}}\times {\frac {1}{8}}\times {\frac {1}{16}}}$) 実際の増加イベントの数は「およそ 32」である可能性が高いですが、任意に高くなる可能性もあります (実際の数が 39 を超える確率は低下します)。

このアルゴリズムは手動で実装できます。カウンターをインクリメントする際は、カウンターの現在の値に対応する回数だけコインを投げます。毎回表が出た場合はカウンターをインクリメントします。そうでない場合はインクリメントしません。

これはコンピュータ上で簡単に実現できます。${\displaystyle c}$カウンターの現在の値とする。${\displaystyle c}$擬似乱数ビットを使用し、それらのビットすべての論理ANDを使用して、結果をカウンタに追加します。擬似乱数ビットのいずれかがゼロの場合、結果はゼロになるため、増加確率は$2-c$この手順は、カウンターをインクリメントする要求が行われるたびに実行されます。

このアルゴリズムは、大量のデータストリームからパターンを分析する際に役立ちます。これは、データ圧縮、視覚・聴覚認識、その他の人工知能アプリケーションにおいて特に有用です。

• HyperLogLog

• Morris, R.小さなレジスタにおける多数のイベントのカウント。Communications of the ACM 21, 10 (1978), 840–842
• Flajolet, P.近似計数：詳細な分析. BIT 25, (1985), 113–134
• Fouchs, M.、Lee, CK.、Prodinger, H.、「ポアソン・ラプラス・メリン法による近似計数」