HyperLogLog(カーディナリティ推定)
1. 概要
A. 定義
HyperLogLog(HLL)とは、大規模データストリームにおける異なる要素の個数、すなわちカーディナリティ(cardinality、ユニーク要素数)を、要素全体を保存せずにほぼ定数のメモリ(数 KB)で近似推定する確率的(probabilistic)データ構造・アルゴリズムであり、各要素のハッシュ値に観測される先頭連続 0 ビット(leading zeros)の最大値という統計量を用いて集合の大きさを逆推定する技法である。
HyperLogLog は「この集合に異なる値はいくつあるか(COUNT DISTINCT)」という問いに答える。正確に数えるにはこれまで見たすべてのユニーク要素を集合(HashSet)に保持する必要があり、メモリが要素数 n に比例(O(n))して爆発するが、HLL は要素を保存せず、固定サイズのレジスタ配列に「どれほど稀なハッシュパターンが現れたか」の痕跡だけを残す。その結果、1 個でも 10 億個でもメモリは変わらず(例:約 12KB)、代わりに数 % 程度の相対誤差を甘受する。これは先に扱った [[bloom-filter]] が「所属の有無」を近似するのと異なり「個数」を近似する点で、相互補完的な確率的データ構造である。
HLL の性質は三つに要約される。第一に、メモリが入力規模に依存せず固定である(定数空間)。第二に、要素あたりの処理はハッシュ一回とレジスタ一回の更新のみであり、挿入が O(1) で非常に高速である。第三に、二つ以上のスケッチを損失なく併合でき、分散集計に自然に適合する。その反面、結果は近似値であり、特定要素の削除や正確な積集合計算には適さない。この長所と短所の束が HLL の適用範囲を決める。
B. 登場背景と必要性
Web・モバイル・IoT 環境が拡大するにつれ、「ユニーク訪問者数(Unique Visitor)」「ユニーク検索語数」「接続した異なる IP 数」「イベントの重複排除件数」といったユニーク個数集計が中核指標となった。しかしこの演算は本質的に高価である。正確な COUNT DISTINCT は重複を排除せねばならずこれまで見たすべての値を記憶する必要があり、一日数十億件のログからユニークユーザを数えるには数 GB〜数十 GB のメモリが要る。数千の指標を同時かつリアルタイムに集計せねばならないダッシュボード・広告システムでは、このコストがそのままインフラコストと遅延につながる。
HyperLogLog は「正確な数ではなく ±2% 程度で十分だ」というビジネス現実を工学的に活用する。ユニーク訪問者が 1,000,230 人か 1,000,235 人かは意思決定に影響しないため、メモリを数千〜数百万倍節約する代わりに小さな誤差を受け入れるのが合理的である。特に HLL は併合(merge)が容易という決定的な長所があり、地域・時間・サーバごとに各々集計した結果を損失なく合わせて「全体ユニーク数」を求められる。この加法性(additivity)のおかげで、分散・ストリーミング環境で事実上の標準となった。
正確な集計がなぜ根本的に高価なのかを理解すると HLL の価値が明確になる。COUNT DISTINCT は「すでに見た値か」を毎回判定せねばならないため、正確であるにはこれまでのユニーク値全体をメモリに保持するか(ハッシュセット)、全体をソート・シャッフル(分散集計)せねばならない。データが水平拡張する環境では、この全体状態はノードのメモリ限界とネットワークシャッフルコストという二つの壁に同時にぶつかる。HLL は「ユニーク個数」という単一の統計量だけが必要なら要素全体を記憶する理由はないという洞察でこの壁を迂回する。これは全数調査の代わりに標本で母集団を推定する統計学の発想をデータ構造に溶け込ませたものに等しい。
2. 動作原理と直観
HyperLogLog の核心的な直観はコイン投げに喩えられる。公正なハッシュ関数を通したビット列は、各桁が 0/1 で一様・独立な乱数列のように見える。あるビット列が先頭から連続して k 個の 0で始まる確率は (1/2)^k である。したがって「先頭に 0 が連続 k 個現れるパターンを少なくとも一度見た」なら、異なる値をおおよそ 2^k 個程度は観測しただろうと推定できる。稀なパターンほど多く引いたという証拠である。
この直観を日常に喩えれば、コインを何度も投げたとき「連続で表が 10 回出る」のを目撃したならかなり多く投げただろうと推し量るのと同じである。重要なのは、この推定が重複に影響されないことだ。同じ要素が 100 回入ってもそのハッシュ値は同一で先頭 0 の個数は変わらないため、HLL は「どれだけ多く入ったか(頻度)」ではなく、ただ「どれだけ多様なパターンが現れたか(ユニーク性)」だけを捉える。まさにこの性質が、要素を保存せずとも重複を濾して固有個数だけを数えさせる根本原理である。ただし単一の観測だけでは推定の分散が過大で(2 のべき乗単位でしか推定できないため)そのままでは使えず、以下のバケット平均化が必ず必要となる。
flowchart LR
X["入力要素 x"] --> HASH["ハッシュ関数 h(x) → 64ビット"]
HASH --> SPLIT["上位 b ビット: レジスタ索引 j"]
HASH --> REST["残りビット: 先頭 0 個数 +1 = ρ"]
SPLIT --> REG["レジスタ M[j]"]
REST --> UPD["M[j] ← max(M[j], ρ)"]
UPD --> REG
実際のアルゴリズムは推定の分散を減らすために確率的平均化(stochastic averaging)を用いる。ハッシュ値の上位 b ビットで 2^b = m 個のバケット(レジスタ)の一つを選び、残りのビットから先頭 0 の個数に 1 を加えた値 ρ を求め、当該レジスタにこれまでの最大値だけを保存する。すなわち各レジスタは「このバケットに入った値のうち最も稀だったパターンの強さ」を記憶する。一つの要素が何度入っても ρ の最大値は変わらないため重複は自動的に無視され、これがユニーク個数だけが数えられる理由である。
最終カーディナリティは m 個のレジスタ値の調和平均(harmonic mean)を用いて推定する。算術平均ではなく調和平均を使うことが LogLog を HyperLogLog へ引き上げた核心的改良であり、調和平均が異常に大きいレジスタ値(外れ値)の影響を抑えて推定の分散を大きく下げるためである。
flowchart TB
A["m 個のレジスタ M[0..m-1]"] --> B["Z = (Σ 2^(-M[j]))^(-1) : 調和平均項"]
B --> C["raw E = alpha_m · m^2 · Z"]
C --> D{"推定補正"}
D -->|"E が小さいとき(E ≤ 2.5m)"| E1["線形計数法(LinearCounting)で再推定"]
D -->|"中間区間"| E2["raw E を使用"]
D -->|"非常に大きいとき(32ビット限界付近)"| E3["上限補正"]
E1 --> OUT["最終カーディナリティ推定"]
E2 --> OUT
E3 --> OUT
推定式は E = α_m · m² · (Σ_{j} 2^(−M[j]))^(−1) の形であり、α_m は推定の偏りを正す定数(大きな m で α_m ≈ 0.7213/(1+1.079/m))である。ただし要素数がレジスタ数 m に比べて少なすぎる場合(多くのレジスタが 0 のまま空である場合)この式は大きな誤差を生むため、この小さいカーディナリティ区間では「0 のレジスタ比率」を用いる線形計数法(Linear Counting)に切り替えて補正する。
A. 段階的な挿入例
動作を小さな例で具体化すると直観が鮮明になる。レジスタを m = 4 個(上位 2 ビットで索引)だけ置いたとする。すべてのレジスタは 0 で初期化される。要素 x をハッシュしたところ上位 2 ビットが 10(= 2 番バケット)、残りビットが 0010…なら、残りで先頭 0 が 2 個なので ρ = 2+1 = 3 となり M[2] ← max(0, 3) = 3 となる。続いて入った y の上位 2 ビットが 00(0 番バケット)、残りが 1…なら先頭 0 が 0 個で ρ = 1、M[0] ← 1 となる。同じ x が再び入っても M[2] は max(3,3) = 3 のままなので重複が自然に吸収される。こうして各バケットは、入ってきた値のうち「最も稀だったパターンの強さ」だけを累積記憶する。
核心は、一つのバケットの値が当該バケット要素数の対数に比例する点である。だからデータ構造の名前に「Log」が入り、レジスタが先頭 0 の個数(= 対数値)だけを収めるためレジスタ一つが 5〜6 ビットで十分なのである。m 個のバケットの対数値を調和平均で束ねると全体カーディナリティの対数が出て、そこに補正定数を掛けて実際の推定値を復元する。要するに「稀なパターンを見た = 多く引いた」という統計的証拠を m 個のバケットに分散収集して平均化することで、単一観測の大きな分散を 1/√m 水準に減らすのが HLL の設計思想である。
3. 精度・メモリ設計と Redis の事例
HLL の相対標準誤差(standard error)はレジスタ数 m に対して約 1.04/√mで与えられる。すなわち精度を 2 倍に高める(誤差を半分にする)にはレジスタを 4 倍に増やさねばならず、メモリと精度は二乗関係のトレードオフをなす。この関係が HLL 設計のすべてだと言っても過言ではない。
具体的な数値で見ると設計感覚が明確になる。64 ビットハッシュを仮定するとき、各レジスタに収まる先頭 0 の個数は最大で約 50 余りなので 6 ビットで十分である。レジスタを m = 2^14 = 16,384 個置くとメモリは 16,384 × 6 ビット ≈ 約 12KB であり、標準誤差は 1.04/√16384 = 1.04/128 ≈ 約 0.81% となる。これがまさに Redis の HyperLogLog 構成である ── わずか 12KB で数十億規模のユニーク数を 1% 未満の誤差で数える。同じ作業を正確な集合で処理すると要素あたり数十バイトがかかり数 GB が必要なので、数十万倍以上のメモリ節約である。
ここで「標準誤差 0.81%」の意味を正確に理解することが重要である。これは 1 シグマ(1σ)の期待誤差であって保証された上限ではない。すなわち真値が 1,000 万のとき推定値は平均的に ±約 8 万(0.81%)の範囲に入るが、稀にその 2〜3 倍まで外れることもある。実務では「おおよそ ±1% 水準」と保守的に解釈し、指標の感度が高ければ m を大きくして余裕を持たせるのが安全である。また、レジスタあたりのビット数を増やすことは精度にほとんど影響せず、レジスタの個数 m だけが精度を左右する点も設計上の核心である ── ビット数は収められる最大の先頭 0 個数(= 扱える最大規模)を定めるだけである。
実務パラメータは通常、対数レジスタ数 b(= log₂m)を 4〜16 の間で選ぶ。b が小さければ(例 b=10, m=1024)メモリは数百バイトに減るが誤差が 3% 台に大きくなり、b が大きければ(例 b=16, m=65536)メモリが 48KB に増えるが誤差が 0.4% に減る。指標一つ一つをどの精度で運用するかはこの b の選択で決まり、数千の指標を同時に維持するシステムでは b の差別的配分が全体メモリ予算を左右する。
| 区分 | 正確な集合(HashSet) | HyperLogLog | 比較観点 |
|---|---|---|---|
| メモリ | O(n)、要素数に比例 | O(1)、固定(例 12KB) | HLL は 10 億個でも 12KB |
| 結果 | 正確 | 近似(標準誤差 ~0.81%) | 小さな誤差を甘受 |
| 併合 | 和集合後に再計算 | レジスタごと max で即時併合 | HLL が分散に有利 |
| 削除 | 可能 | 不可(追加・併合専用) | HLL は集計専用 |
| 積集合 | 正確 | 包除で近似(誤差大) | HLL の弱点 |
表のとおり HLL の最大の実務的利点は併合の単純さである。二つの HLL を合わせるには同じ索引のレジスタ同士でより大きい値を取る(max)だけでよく、これは交換・結合法則を満たしMapReduce・ストリーミング集計の reduce 段階に完璧に適合する。例えば 100 台の Web サーバが各々自分のトラフィックの HLL を作った後、中央で 100 個を max で合わせれば全体のユニーク訪問者が出て、この過程は元ログを一か所に集める必要がなくネットワーク・保存コストを大きく減らす。一方積集合(共通ユーザ数)は HLL だけでは直接求められず包除原理で近似せねばならず誤差が累積するため、積集合が核心なら MinHash など他の技法を併用せねばならない。
4. 類似技法の比較と発展:HyperLogLog++
HyperLogLog は 1984 年の Flajolet–Martin アルゴリズムから出発し、2003 年の LogLog、2007 年に Flajolet らが提案した HyperLogLog へ発展し、2013 年に Google が大規模実務適用のために改良した HyperLogLog++(HLL++) で頂点に達した。各段階は「同じメモリでいかに誤差をさらに減らすか」の工学的改良の歴史である。
HLL++ の核心的改良は三つある。第一に、ハッシュを 32 ビットから64 ビットへ拡張し、数十億を超える非常に大きなカーディナリティで生じていたハッシュ衝突(上限飽和)問題を事実上除去した。第二に、元の HLL が小さいカーディナリティ区間で大きな偏りを示していた問題を、事前に測定した経験的偏り表(empirical bias correction)で補正し精度を引き上げた。第三に、要素数が少ないときは 16,384 個のレジスタの大半が空でメモリが無駄になるため、初期には観測値を疎表現(sparse representation)のみで保存し、大きくなると密(dense)レジスタに切り替えて小さいカーディナリティでメモリをさらに節約する。この HLL++ が今日、Google BigQuery の APPROX_COUNT_DISTINCT、Presto/Trino の approx_distinct、Apache Druid、Elasticsearch の cardinality 集計など商用分析エンジンの基盤となった。
| アルゴリズム | 登場 | 平均化方式 | 相対誤差 | 特徴 |
|---|---|---|---|---|
| Flajolet–Martin | 1984 | 単一ビットマップ | 大きい | 最初の確率的計数 |
| LogLog | 2003 | 算術平均 | 1.30/√m | レジスタあたり少数ビット |
| HyperLogLog | 2007 | 調和平均 | 1.04/√m | 分散を大幅に減少 |
| HyperLogLog++ | 2013 | 調和平均+補正 | 1.04/√m(低区間改善) | 64ビット・偏り補正・疎表現 |
A. 隣接する確率的データ構造との役割区分
HLL は「確率的スケッチ(sketch)」系列の一軸にすぎず、問う質問が異なれば選択も異なる。混同を避けるには「何を近似するのか」を基準に区分せねばならない。ブルームフィルタは所属(membership)(「この値は集合にあるか」)を、HyperLogLog はカーディナリティ(「ユニーク要素はいくつか」)を、Count–Min Sketch は頻度(「この値は何回現れたか」)を、MinHash・Theta Sketch は類似度・積集合(「二つの集合はどれほど重なるか」)を近似する。質問を誤ってマッピングすればいくらチューニングしても望む答えは出ない。
| スケッチ | 近似対象 | 典型的な質問 | HLL との関係 |
|---|---|---|---|
| ブルームフィルタ | 所属 | 「見たことがあるか」 | 補完(存在の有無) |
| HyperLogLog | ユニーク個数 | 「何種類か」 | 本主題 |
| Count–Min Sketch | 頻度 | 「何回出たか」 | 補完(頻度) |
| MinHash/Theta | 積集合・類似度 | 「どれほど重なるか」 | HLL の弱点を補完 |
実務ではこれらを組み合わせて使う。例えばトラフィック監視でブルームフィルタで新規 IP を濾し、HLL でユニーク IP 数を数え、Count–Min Sketch で上位トラフィック IP(heavy hitter)を追跡する具合である。各スケッチが固定メモリで特定の統計量だけを近似するという共通の設計哲学を共有するため、大規模ストリーム分析の標準ツールボックスとして共に束ねられる。
5. 深化:実務適用と最新の活用動向
HyperLogLog は「近似してよいユニーク計数」という広い需要のおかげでデータプラットフォームの基本機能として定着した。代表事例として Redis は PFADD(要素追加)・PFCOUNT(推定照会)・PFMERGE(併合)の三つのコマンドで HLL を提供し、接頭辞 PF は HyperLogLog を創案した Philippe Flajolet を讃えたものである。リアルタイムのユニーク訪問者ダッシュボード、API 呼び出しのユニーククライアント数、広告表示のユニーク到達(reach)集計などに幅広く使われる。
具体的な規模感を挙げると、一日 1 億件のリクエストを受けるサービスが 1 分単位でユニークユーザ数を集計するとしよう。正確な集計は分あたり数十万個のユニーク ID をメモリに保持し、真夜中に一日分を合わせねばならないが、HLL は分あたり 12KB のスケッチ一つで済み、一日分(1,440 個)をすべて集めても約 17MB にすぎず、任意区間のユニーク数を併合だけで即時に得る。保存・演算・照会の三つのコストが同時に数百倍以上減るわけである。
データウェアハウス領域では、正確な COUNT(DISTINCT) がシャッフル・ソートコストで大型テーブルで遅くなる問題を HLL ベースの近似関数で解決する。例えば数百億行のログから日別ユニークユーザ推移を毎時更新せねばならないとき、正確な集計はクエリあたり数分〜数十分かかりうるが、APPROX_COUNT_DISTINCT は数秒〜数十秒で 1% 内外の誤差で答える。コストが課金されるクラウド分析環境ではスキャン・演算量の減少がそのまま料金節約なので、経済的効果は直接的である。
さらに、HLL スケッチを中間成果物として保存しておくパターンが広く使われる。元テーブルを毎回スキャンする代わりに、時間単位で HLL スケッチを事前に作り別テーブル(あるいは Redis キー)に積載しておけば、日間・週間・月間のユニーク数は当該区間のスケッチを併合(PFMERGE・HLL_UNION)するだけでほぼ即時に計算される。これは正確な集計では不可能な戦略で、HLL が「集計結果を再利用・再結合可能な形で保存する」点を活用したものである。その結果、バッチ再計算コストとリアルタイム照会遅延を同時に下げられる。
最新動向としては、① HLL を時系列データベースに組み込みロールアップ(roll-up)段階でユニーク数を事前集計する方式、② 異なる軸(地域×端末×キャンペーン)を組み合わせて問う多次元ユニーク集計を HLL スケッチを事前に作って併合で処理する方式、③ プライバシー強化のために HLL スケッチにノイズを加えて差分プライバシー(Differential Privacy)と結合する研究がある。ただし HLL スケッチ自体が個人識別情報を含まなくとも、特定の条件で小規模集合の所属を逆推論できる可能性についての議論があり、機微データには慎重な設計が求められる。
多次元ユニーク集計は HLL の併合性が光る代表的なパターンである。例えば広告プラットフォームが「キャンペーン A のソウル地域の Android ユーザのうちユニーク到達数」のように軸を組み合わせて問うクエリに毎回元を再スキャンすればコストが爆発する。代わりに(地域, 端末, キャンペーン)の細かな組み合わせごとに HLL スケッチを事前に作って保存しておけば、上位クエリは該当する下位スケッチを max 併合して即時に答えられる。正確な COUNT DISTINCT では組み合わせごとに再び重複排除をせねばならずこうした事前集計・再結合(pre-aggregation & roll-up)が不可能である点で、HLL は OLAP キューブ型分析に構造的に有利である。
さらにストリーミング処理フレームワーク(Apache Flink・Spark Structured Streaming)では、ウィンドウごとのユニーク数を HLL スケッチで維持し、ウィンドウが閉じるとき推定値だけを出力する方式で状態(state)サイズを定数に束ねる。無限に入ってくるストリームでは正確な集計は状態が無制限に大きくなるが、HLL はウィンドウあたり固定サイズなので長期運用でもメモリが暴走しない。この「有限状態で無限ストリームを要約する」性質が HLL をリアルタイム分析の標準要約(sketch)にしたもう一つの理由である。
6. 考慮事項と示唆点
技術士の観点から HyperLogLog の導入は次を総合的に考慮せねばならない。
誤差許容性と指標の性格をまず判断する。 HLL は ±1〜2% の誤差が許容されるトレンド・規模指標(ユニーク訪問者、到達数)に適する。課金・精算・規制報告のように正確性が法的・金銭的に要求される集計には適さず、必ず正確な集計または事後の整合性検証経路を併用せねばならない。
精度目標に合わせてレジスタ数 m を事前算定する。 誤差が 1.04/√m でメモリが m に比例するため、目標誤差を半分に減らすにはメモリが 4 倍かかる。すべての指標に高精度を適用するより、指標ごとの重要度に応じて精度(メモリ)を差別配分する設計が費用対効果に優れる。
併合可能性という長所をアーキテクチャに反映する。 HLL の max 併合は交換・結合法則を満たすため分散収集・ストリーミング集計に理想的である。エッジ・サーバごとにスケッチを作り中央で併合すれば元ログの移動を避けられ、[[edge-computing]] およびデータ局所性(data locality)戦略とよく結合する。ただし異なる m・ハッシュで作ったスケッチは併合できないためパラメータ標準化を先行せねばならない。
積集合・差集合の要求を初期に確認する。 HLL は和集合(併合)には強いが積集合は包除で近似せねばならず誤差が累積する。「二つのセグメントの共通ユーザ数」が核心指標なら HLL 単独では適さず、MinHash・Theta Sketch などを併せて検討せねばならない。
削除不可・プライバシー特性を考慮する。 HLL は要素を消せない追加・併合専用構造なので、特定ユーザの集計除外(撤回権対応など)が必要なら再計算または別途の設計が要る。またスケッチが識別情報を直接含まなくとも、機微ドメインでは逆推論リスクを評価し必要に応じてノイズ・アクセス制御を併用する。
ハッシュ関数の品質とパラメータ互換性を標準化する。 HLL の理論誤差はハッシュが十分に一様・独立という仮定の上で成り立つため、偏ったハッシュや短いハッシュは実際の誤差を理論値より悪化させる。MurmurHash・xxHash のような高速・高品質な非暗号学的ハッシュを使うが、異なるシステムが作ったスケッチを併合するにはハッシュ関数・レジスタ数・符号化規約が完全に同一でなければならない。この規約を組織レベルで標準化しなければ、後になってスケッチを再生成せねばならないコストが生じる。
総合すると、HyperLogLog は「正確性の一部を差し出してメモリと併合性という実質的利得を得る」工学的近似の代表事例であり、データ規模が爆発する AI・ビッグデータ環境で固定メモリでユニーク計数を線形拡張させる中核ツールである。導入時には誤差許容性、目標精度に応じたメモリ算定、併合・積集合の要求、削除・プライバシー制約を基準に適用範囲を設計することが成否を分ける。
参考資料
- Salvatore Sanfilippo(antirez), "Redis new data structure: the HyperLogLog", https://antirez.com/news/75
- Flajolet, Fusy, Gandouet, Meunier, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm"(2007), http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
- Heule, Nunkesser, Hall, "HyperLogLog in Practice"(Google, EDBT 2013), https://research.google/pubs/pub40671/
一言まとめ: HyperLogLog はハッシュ値の先頭 0 の最大値をレジスタ配列に記録し調和平均で逆推定することで、数 KB の固定メモリで数十億規模のユニーク要素数を約 1% の誤差で数える確率的カーディナリティ推定技法である。