Flajolet–Martin algorithm とは

Flajolet-Martinアルゴリズムは、ストリーム内の可能な別個の要素の最大数(カウント別の問題)において、単一のパスおよびスペース消費対数を用いて、ストリーム内の別個の要素の数を近似するためのアルゴリズムです。このアルゴリズムは、Philippe FlajoletとG. Nigel Martinによって、1984年の記事「データベースベースアプリケーションの確率的計数アルゴリズム」で紹介されました。その後、Marianne DurandとPhilippe Flajoletによる「大規模なカーディナリティのログログカウント」、および「HyperLogLog:Philippe Flajoletらによる最適最適化カーディナリティ推定アルゴリズムの分析」で洗練されました。
2010年の記事「別個の要素問題の最適アルゴリズム」では、Daniel M. Kane、Jelani Nelson、David P. Woodruffが最適な領域を使用し、最適なO(1)更新と報告時間を持つ改良アルゴリズムを示しています。