確率的データ構造（Bloom・HLL・Count-Min）

なぜ「正確」を捨てると桁で軽くなるのか

大規模データの集計には、避けがたいメモリの下限があります。「このデータセットに含まれるユニークなユーザー数は」を厳密に答えるには、原理的に見た要素をすべて覚える必要があり、要素数nに対しメモリはΩ(n)で増えます。10億ユニークを正確に数えれば、それだけで数十GBのハッシュ集合を抱えることになる。分散基盤ではこれが二重に痛い。各ノードのメモリを食うだけでなく、部分結果を統合するとき巨大な集合をシャッフルで運ぶ羽目になるからです。

確率的データ構造（sketch）は、この下限を答えを近似に緩めることで回避します。厳密な集合の代わりに、値のハッシュから抽出した統計量だけを固定サイズの配列に畳み込む。得られるのは正確な数ではなく、誤差が数式で保証された推定値です。ダッシュボードの「アクティブユーザー数」や「上位検索語」に、小数点以下の正確さは要りません。数%の相対誤差を許すだけで、メモリがKB〜数十KBの定数に落ちる。これがスケッチの取引です。

ブルームフィルタ：ビット配列に「集合の影」を焼く

ブルームフィルタは存在判定に特化した集合です。「この要素は集合に入っているか」に、入っていない（確実）またはたぶん入っている（偽陽性あり）で答えます。実体はmビットの配列とk個の独立なハッシュ関数だけ。

• 追加：要素xについて h1(x)..hk(x) mod m のk箇所のビットを1に立てる。
• 問い合わせ：同じk箇所を見て、すべて1なら「たぶん有る」、1つでも0なら「確実に無い」。

要素そのものは一切保存しないので、偽陰性は原理的に起きません（追加時に立てたビットが勝手に0へ戻ることはない）。一方、無関係な要素群がたまたまk箇所すべてを他の要素で埋めていれば、偽陽性が出ます。

m=16, k=3 のビット配列
  add("A"): h→ 2, 7,13 を 1 に
  add("B"): h→ 5, 7, 9 を 1 に
  query("A"): 2,7,13 すべて1 → たぶん有る（真陽性）
  query("Z"): 5,9,13 が偶然すべて1 → たぶん有る（偽陽性！ Zは未追加）
  query("Q"): 4 が 0    → 確実に無い

偽陽性率は解析的に出ます。n要素を入れた後、あるビットが0のままの確率は (1 - 1/m)^(kn) ≈ e^(-kn/m)。問い合わせのk箇所がすべて1になる確率、すなわち偽陽性率pは概ね p ≈ (1 - e^(-kn/m))^k。ここから設計式が導けます。目標pと想定nに対し、必要ビット数は m ≈ -n·ln(p)/(ln 2)^2、最適なハッシュ本数は k ≈ (m/n)·ln 2。例えば偽陽性1%なら1要素あたり約9.6ビット、0.1%でも約14.4ビットで足り、要素の実サイズと無関係に一定なのが要点です。

HyperLogLog：基数を「最長の先頭ゼロ列」から当てる

「ユニーク数（基数, cardinality）」の推定はHyperLogLog（HLL）の担当です。発想の核は確率です。各要素をハッシュして一様なビット列にすると、先頭に連続する0がρ個続く確率は 2^(-(ρ+1))。多数の異なる要素を流せば、いつかは長い先頭ゼロ列が現れる。観測した最長の先頭ゼロ列がρ_maxなら、見たユニーク数はおおよそ 2^ρ_max と当たりを付けられます。1つのカウンタは分散が大きすぎるので、HLLはハッシュの先頭数ビットで要素を m = 2^p 個のレジスタへ振り分け、各レジスタが担当分の最長先頭ゼロ列を保持し、全レジスタの推定を調和平均でならして分散を潰します。

m = 4 レジスタ（先頭2ビットでバケット選択、残りで先頭ゼロ数ρを測る）
  要素ごとに: b = 先頭2ビット, ρ = 残りビットの (先頭0連続数 + 1)
  register[b] = max(register[b], ρ)   ← 最大値だけ更新
  推定基数 ≈ α_m · m^2 / Σ_j 2^(-register[j])   （調和平均ベース）

精度はレジスタ数だけで決まり、相対標準誤差は約 1.04/√m。p=14（m=16384レジスタ）なら誤差は約0.8%で、各レジスタは6ビットあれば足りるので全体で約12KB。これで基数が数十億でも同じサイズで概算できます。基数がmに比して小さい領域では推定が偏るため、実務のHLL++は小基数域を線形カウンティングへ切り替え、疎表現でメモリをさらに節約します。

Count-Min：頻度を「複数ハッシュの最小値」で読む

Count-Minスケッチは各要素の出現頻度（および上位頻出＝ヘビーヒッター）を推定します。構造はd行×w列のカウンタ二次元配列と、行ごとに1つずつ、計d個の独立なハッシュ関数。

• 更新：要素xの出現時、各行iで count[i][hi(x) mod w] を1増やす（d箇所を加算）。
• 問い合わせ：同じd箇所を見て、その最小値を頻度推定とする。

なぜ最小値か。ハッシュ衝突は必ずカウンタを増やす方向にしか働かない（他の要素が同じセルに乗ると値が水増しされる）ため、各行の推定は真の頻度以上になります。d個の独立な推定のうち最小のものが、最も衝突汚染の少ない値。ゆえにCount-Minの誤差は**常に過大側（片側）**で、過小評価は起きません。

d=2 行 × w=5 列
  add("A") 3回, add("B") 1回, hがぶつかると同一セルを共有
    行0: [ .. A+B=4 .. ]      ← A,B が同じ列に衝突
    行1: [ .. A=3 .. B=1 .. ] ← 別の列に分離
  query("A") = min(4, 3) = 3   ← 正しい（過大側の4を最小で回避）

誤差保証は明快です。幅wと深さdに対し、加法的な過大誤差は総更新回数Nに比例して 推定 ≤ 真値 + ε·N、ここで ε = e/w、この保証が破れる確率は δ = e^(-d)。つまり幅wが誤差の大きさを、深さdが失敗確率を独立に制御します。例えば w=2000, d=5 なら約40KBで、ε≈0.14%・信頼度 1 - e^(-5)≈99.3%。頻度の高い要素ほど相対誤差は小さく、ヘビーヒッター検出に向く一方、低頻度要素は衝突ノイズに埋もれやすい点が構造的な限界です。

加法性：スケッチが分散集計に噛み合う本当の理由

三つのスケッチが分析基盤で価値を持つ決め手は、精度以上に加法性（mergeability）です。分散集計は「各パーティションで部分集約し、結果を統合する」形を取りますが、素朴な正確集計では中間状態（ユニーク値集合など）が大きく、統合段のシャッフルが律速になります。スケッチは中間状態が定数サイズで、しかも単純な要素ごとの演算で損失なく結合できます。

この加法性は代数的にはMapReduceのcombinerが要求する結合則・交換則そのものです。だからスケッチは、map側の事前集約でも、reduce側の統合でも、同じ演算で安全に畳み込める。Sparkのパーティションごとに部分スケッチを作り treeAggregate で二分木状に統合しても、結果は全データを1つのスケッチに通したものと一致します。さらに定数サイズゆえに保存して後から結合できる。日次のHLLを保存しておけば、任意期間の週次・月次UUを、生データを読み直さずレジスタのmaxだけで算出できます。これが正確なDISTINCTでは（日次のユニーク集合和が必要で）成り立たない、スケッチ特有の運用上の強みです。

トレードオフの設計：どの誤りを、いくら許すか

三つは「近似で軽くする」点は同じでも、答える問い・誤りの向き・サイズの決定要因が異なります。設計とは、用途ごとに「許せる誤りの種類と量」を選び、それに対応するパラメータを逆算する作業です。

いずれも「メモリを増やすほど誤差が縮む」交換関係を持ちますが、縮み方が違います。ブルームとCount-Minは誤差が要素数・更新回数に相対的で、想定規模nやNを見積もってサイズを取る必要があります（見積もりを超えると劣化する）。対してHLLは入力規模に依存せず、レジスタ数mだけで相対精度が決まる——数千でも数十億でも同じ12KBで同じ0.8%というスケール非依存性が、基数推定でHLLが定番化した理由です。ストリーミングで長時間走らせるなら、規模想定が要らないHLLの安定性は運用上も効きます。

まとめ

• 確率的データ構造は、正確な集計に要る線形メモリの下限を、定量化された誤り率と引き換えに定数〜対数サイズへ落とす。1パス・有界メモリ・加法性の三点で、ビッグデータの近似集計に噛み合う。
• ブルームフィルタは存在判定に特化し、偽陰性を出さず偽陽性率は約 (1-e^(-kn/m))^k。無駄なI/Oや結合相手を読む前に安全に枝刈りする前段フィルタとして効く。
• HyperLogLogは先頭ゼロ列の確率から基数を当て、相対誤差は約 1.04/√m。約12KBで数十億ユニークを概算でき、APPROX_COUNT_DISTINCT の実体として正確なDISTINCTのシャッフル爆発を回避する。
• Count-Minはd×wカウンタと最小値読みで頻度を推定し、誤差は過大側のみ（ε=e/w、失敗確率 δ=e^(-d)）。ヘビーヒッター検出に向くが低頻度要素は衝突に埋もれる。
• 分散集計での決め手は加法性：BloomはOR、HLLはmax、Count-Minは加算で、部分スケッチを損失なく結合できる。これはcombinerやtreeAggregateが要求する結合則そのもので、保存して任意期間を後から結合する運用も成り立つ。ただし同一パラメータ同士しか結合できず、保証は一様ハッシュに依存する。