HyperLogLogはキロバイト単位で数十億の異なる項目を数えた

正確なカーディナリティ — 何人の異なるユーザー、IPアドレス、検索クエリが現れたか — は通常、異なる項目の数に比例するメモリを必要とし、インターネット規模では不可能である。2007年、INRIAのPhilippe Flajoletと同僚たちはHyperLogLogを発表した。これは約1.5キロバイトのメモリで約2パーセントの精度で10億を超えるカーディナリティを推定する確率的スケッチである。

このトリックはコイントスの直感に基づく。すべての要素を一様な乱数にハッシュ化し、先頭ゼロの最長連続を監視する。n個のゼロの連続は稀であり — 確率は2^-n — それが現れるとき、集合はおそらくそれを生み出すのに十分な大きさであり、2^nがカーディナリティの良い推定値となる。HyperLogLogはストリームを多数の部分集合に分割し、各部分集合ごとに最長ゼロ連続を保持する1つのレジスタを維持し、それらを調和平均で結合することで外れ値が推定を歪めないようにする。

この手法はFlajolet-Martinの1984年のアルゴリズムとLogLogアルゴリズムに由来する。それを実運用可能にしたエンジニアリングは、GoogleのHeule、Nunkesser、Hallによる2013年の論文「HyperLogLog in Practice」で登場し、大規模および小規模なカーディナリティに対するバイアスと疎性の問題を修正した。

RedisはHyperLogLogを製品機能にした。そのPFADD、PFCOUNT、PFMERGEコマンドは、キーあたり最大12KBのメモリと0.81パーセントの標準誤差で最大2^64の異なる要素を推定し、スケッチはマージされるため、生のストリームを再読み込みすることなく日次カウントを結合できる。

ハッシュの先頭ゼロからカウントを推定する

ハッシュは任意のデータを同じカーディナリティを持つ一様な乱数に変える

先頭ゼロの最長連続は集合サイズの自然で観測可能な推定値である

レジスタへの分割と調和平均がノイズを打ち消す

スケッチはマージできるため、生のストリームを保存せずに日次カウントを結合できる

答えが近似でよいなら、データを保存するのをやめよ — ランダム性がサイズを明らかにする小さなスケッチを保存し、有界の誤差を無限のスケールと引き換えにせよ。

HyperLogLogは分析とデータベースにおける標準的な構成要素となった。Redisはそれをデータ型として提供し、2013年のGoogleの論文の改善が、実運用システムで大規模に使用可能にしたものである。このスケッチの論理 — データではなく証拠の小さな記録を保持する — は、MinHashやCount-Min Sketchのような後の構造の基盤にもなっている。