Count-Min Sketch(頻度推定スケッチ)
1. 概要
A. 定義
Count-Min Sketch(CMS)とは、大規模データストリームにおいて各要素が何回出現したか(頻度、frequency)を、要素ごとのカウンタをすべて保持せずに固定サイズの2次元カウンタ配列と複数のハッシュ関数だけで近似推定する確率的(probabilistic)データ構造であり、問い合わせ時に複数行のカウンタのうち最小値(min)を取ることで、ハッシュ衝突による過大推定を抑制する手法である。
Count-Min Sketchは「この要素はこれまで何回現れたか」という問いに答える。正確に数えるには出現したすべての一意キーごとにカウンタを置く必要があるため、異なるキーが数億個あればメモリもそれだけ大きくなる(O(一意キー数))。CMSはキーを保存せず、幅w・深さdの小さな整数配列1枚に複数キーの頻度を重ねて記録する。その結果、一意キーが1万個でも10億個でもメモリは変わらず、その代わり衝突による過大推定(overestimation)という小さな誤差を甘受する。これは先に扱った[[bloom-filter]]が「所属の有無」、[[hyperloglog]]が「一意個数」を近似するのと異なり、CMSは「頻度(個数)」を近似するという点で、3つのデータ構造が互いに補完的な確率的要約(sketch)系列をなす。
CMSの性質は4つに要約される。第一に、メモリが入力規模・一意キー数に依存せず固定である(定数空間)。第二に、挿入・問い合わせがそれぞれハッシュd回とカウンタd回のアクセスだけなので、O(d)で非常に速く、dは通常数〜十程度の小さな定数である。第三に、同じ幅・深さ・ハッシュを使う2つのスケッチを要素ごとの加算で無損失にマージでき、分散集計に自然に適合する。第四に、負数のない(カウント増加のみの)場合、推定値は常に真値以上であり決して過小推定しない。この4つの性質の束がCMSの適用範囲を決定する。
B. 登場背景と必要性
ウェブ・広告・通信・金融のログが毎秒数十万件で降り注ぐ環境では、「どのURLが最も多く呼ばれるか」「どの送信元IPが異常に多くのパケットを送るか」「どの検索語が急上昇するか」といった頻度問い合わせと上位頻出項目(heavy hitter)検出が中核の運用指標となった。しかし正確な頻度集計は本質的に高価である。すべてのキーごとにカウンタを維持しなければならないため、1日数十億件のログで一意キーが数億個あれば数GB〜数十GBのハッシュマップが必要となり、これをリアルタイムに更新・問い合わせするとメモリ圧迫とGC遅延がそのままサービスコストになる。
Count-Min Sketchは「正確な頻度ではなく相対誤差が数%以内であれば十分だ」という運用現実を工学的に活用する。あるIPが正確に1,000,230回接続したか1,000,245回接続したかは「このIPが閾値を超えるヘビーヒッターか」を判定するのに影響しないため、メモリを数十〜数千倍節約する代償として小さな過大推定を甘受するのが合理的である。特にCMSはマージが容易だという決定的な利点のおかげで、サーバ・時間帯・シャードごとに個別集計したスケッチを損失なく合わせて全体頻度を復元でき、分散・ストリーミング環境で事実上の標準要約構造として定着した。
正確な集計がなぜ根本的に高価なのかを理解すれば、CMSの価値が明確になる。正確な頻度表は「これまで見たすべてのキー」を記憶しなければならないため、キー空間が開いていて(例:任意の文字列・IP・URL)分布がロングテールであればカウンタ数が爆発する。データが水平にスケールする環境では、この全状態はノードメモリの限界とネットワークシャッフルのコストという2つの壁に同時にぶつかる。CMSは「頻度という単一の統計量だけが必要なら、キーを一つ一つ記憶する理由はない」という洞察で、複数キーを同じカウンタに重ねて積みつつ衝突の影響を統計的に抑制し、この壁を回避する。
C. 特徴
CMSは過小推定が決してないという一方向の誤差構造を持つ。これは「閾値を超えたら警報」のように見逃し(false negative)を許容できない検出に特に有利である。一方、あるキーが稀にしか出現しなくても他の頻出キーと衝突すればその頻度が膨らんで見えうるため、希少キーの推定が相対的に不正確だという限界がある。また基本形は挿入・問い合わせのみを支援し、削除(負数更新)を許すとminの一方向保証が崩れるため、別途の変形が必要である。
構造的にCMSは[[bloom-filter]]と深い親縁性を持つ。ブルームフィルタがビットを立てる位置にCMSは整数カウンタを置き、「立ったか」を「どれだけ積まれたか」に一般化したものと見られる。実際、カウンタを1ビットに縮めればブルームフィルタに、問い合わせをminの代わりにORに変えれば所属問い合わせに収束する。この見方は「同じハッシュ重ね構造の上で何を数えどう集計するか」がデータ構造の用途を決定するという設計原理を示し、3つの確率的要約(ブルーム・HLL・CMS)を一つの思考枠組みにまとめる。
2. 構造と動作原理
Count-Min Sketchの核心は、「一つのキーをd個の異なるハッシュでd個のカウンタに分散記録し、問い合わせの際はそのd個のうち最小値を信じる」ことである。衝突で特定のカウンタが膨らんでいても、d個すべてが同時に激しく衝突する確率は非常に低いので、最小値は真値に近い。これは複数回測って最も小さく出た値を信頼するのと同じ発想で、「衝突は値を増やすだけ」という一方向性のおかげで最小値が最も汚染の少ない推定となる。
flowchart TB
X["入力 (キー x, 増加量 c)"] --> H1["ハッシュ h1(x) → 列 j1"]
X --> H2["ハッシュ h2(x) → 列 j2"]
X --> HD["ハッシュ hd(x) → 列 jd"]
H1 --> R1["行1: C[1][j1] += c"]
H2 --> R2["行2: C[2][j2] += c"]
HD --> RD["行d: C[d][jd] += c"]
subgraph TABLE["カウンタ配列 d行 x w列"]
R1
R2
RD
end
データ構造は、d個の行(深さ、depth)× w個の列(幅、width)からなる整数カウンタ2次元配列 Cと、互いに独立なd個のハッシュ関数h₁…h_dで構成される。各ハッシュはキーを[0, w)の範囲の列インデックスへ写像する。各行は独立した一つの「近似頻度表」であり、行同士は異なるハッシュを使うので、ある2つのキーが1行で衝突しても2行・3行では大抵衝突しない。まさにこの行間独立性がd個の推定の最小値を信頼できる根拠である。
更新(Update)演算 Update(x, c) は各行i(=1…d)に対して列インデックスhᵢ(x)を求め、C[i][hᵢ(x)]にcを加える。ストリームで要素が来るたびに通常c=1だが、重み付きログであれば任意の正数cを加えられる。一つのキーは各行で正確に1マスだけ触れるので、更新コストは入力規模に依存せずO(d)で一定である。例えばd=4なら1イベントあたりハッシュ4回・加算4回で済み、毎秒数百万件のストリームも単一ノードで処理できる。
問い合わせ(Query)演算 Query(x) は各行でC[i][hᵢ(x)]を読み、そのd個の値の最小値を推定頻度f̂(x)として返す。あるキーxの真の頻度をf(x)とすれば、xが記録されたすべてのカウンタには少なくともf(x)が入っており、そこに他のキーの寄与が加わるので、すべての行でC[i][hᵢ(x)] ≥ f(x)が成り立つ。したがってその最小値もf(x)以上であり、これが過大推定は可能だが過小推定は不可能だというCMSの核心的保証である。
小さな例で直観を固めよう。d=2、w=4のスケッチにキーAが5回、Bが3回、Cが2回入ったとしよう。1行でハッシュh₁がAとCを同じ列へ送れば、その列には5+2=7が積まれ、Aを1行だけ見て問い合わせると7で2だけ過大推定される。しかし2行のハッシュh₂がAをB・Cと異なる列へ送っていれば、その列は正確に5であり、問い合わせはmin(7, 5)=5で真値を復元する。このように一つの行の衝突が他の行の「きれいな」カウンタで補正されるのがmin演算の効用であり、行数dを増やすほどすべての行が同時に汚染される確率が指数的に減り、推定が安定する。
3. 問い合わせ処理フローとヘビーヒッター検出
CMS単独では「特定キーの頻度」だけを答えられ、「上位K個の頻出項目は何か」は直接答えられない。実務で最も多い要求がまさにヘビーヒッター(heavy hitter)検出であるため、CMSは通常小さな最小ヒープ(min-heap)またはTop-K構造と結合して使う。以下のフローはストリーム要素を受けてスケッチを更新し、推定頻度がヒープの下限を超えれば候補へ昇格する典型的なパイプラインである。
flowchart LR
S["ストリーム要素 x"] --> U["CMS.Update(x, 1)"]
U --> Q["est = CMS.Query(x)"]
Q --> D{"est > ヒープ最小値?"}
D -- "はい" --> P["Top-K ヒープに x, est を反映"]
D -- "いいえ" --> N["無視"]
P --> O["周期的に上位 K 頻出項目を出力"]
N --> O
この構造でCMSは「すべてのキーの近似頻度を定数メモリで維持」する役割を、ヒープは「そのうち上位K個だけを選んでソート保持」する役割を担う。ヒープサイズはKで固定されるので全体メモリは依然として定数である。例えば通信事業者が1分ウィンドウ([[stream-processing-windowing]])ごとに上位100個の宛先IPを抽出するなら、数百万の一意IP全部の正確な表の代わりに数MBのCMSと100マスのヒープだけで十分である。ただし過大推定のために希少キーが時折ヒープに誤って上がりうるので、閾値に余裕(margin)を置くかウィンドウ終了時に精密検証を付け足す設計が使われる。
ヘビーヒッター検出で必ず押さえるべき点は、CMSが「推定頻度が閾値以上の候補」は漏れなく捕捉するが(見逃しなし)、候補の一部は衝突で膨らんだ偽でありうるという非対称性である。したがって実務パイプラインは「CMSで一次候補を安く篩い(再現率100%)、二次に精密カウンタ・サンプリングで検証(精度補正)」する2段階構造をよく採る。これは高価な正確集計を全体ではなく少数の候補にのみ適用させ、コストと正確性を同時に押さえる典型的な近似-精密結合パターンである。
マージ可能性(mergeability)も問い合わせフローの重要な軸である。シャードAとシャードBがそれぞれCMS_A、CMS_Bを維持したなら、2つの配列を同じ座標どうしで加えたCMS_A+Bは「全体ストリームを一つのスケッチで処理したもの」と数学的に同一である。おかげでMapReduce・Spark系の分散集計で各パーティションがローカルスケッチを作りreduce段階で加えるだけでよく、生データをシャッフルするコストを無くせる。この加法性は[[hyperloglog]]とともにCMSを分散環境の標準要約にした決定的な性質である。
4. 誤差限界とパラメータ設計
CMSの誤差は偶然ではなく厳密な確率的上限で制御される。全体ストリームの総頻度和(L1ノルム)をN = Σf(x)とし、幅をw、深さをdと置けば次が成り立つ。一つの行でキーxのカウンタに混ざり込む他キーの期待寄与はおよそN/wである(総量Nがw個の列に均等に広がるという直観)。マルコフの不等式を適用すると、一つの行の過大推定がεNを超える確率は(N/w)/(εN) = 1/(εw)である。幅をw = ⌈e/ε⌉に取ればこの確率は1/eとなり、d個の行が独立なのですべての行が同時にεNを超過する確率は(1/e)^d = e^(−d)となる。これを失敗確率δ以下にするには深さd = ⌈ln(1/δ)⌉で十分である。
整理すると、w = ⌈e/ε⌉、d = ⌈ln(1/δ)⌉のとき推定値はf(x) ≤ f̂(x) ≤ f(x) + εN を確率1−δ以上で保証し、空間はO((1/ε)·ln(1/δ))カウンタで固定される。例えばε=0.001(総量の0.1%)、δ=0.001(99.9%信頼)を望むなら、w ≈ ⌈e/0.001⌉ = 2,719、d = ⌈ln(1000)⌉ = 7となり、約2,719×7 ≈ 19,033個のカウンタ(4バイト整数なら約76KB)だけで数億キーの頻度を近似できる。一意キー数に依存せずメモリがこの水準で固定されるという点がCMSの実務的な魅力である。
| パラメータ | 意味 | 公式 | 大きくなると/小さくなると |
|---|---|---|---|
| ε (イプシロン) | 許容誤差比率(εN) | 入力要件 | 小さいほど正確、w増加 |
| δ (デルタ) | 保証失敗確率 | 入力要件 | 小さいほど信頼↑、d増加 |
| w (幅) | 列の数 | ⌈e/ε⌉ | 大きいほど衝突↓・メモリ↑ |
| d (深さ) | 行・ハッシュの数 | ⌈ln(1/δ)⌉ | 大きいほど信頼↑・問い合わせコスト↑ |
ここで必ず留意すべき点は、誤差上限が絶対量εNに比例するという事実である。Nが大きい高頻度ストリームほどεNも大きくなるので、頻繁なキー(ヘビーヒッター)は相対誤差が小さいが、希少なキーはεNに埋もれて相対誤差が大きくなる。これはCMSが設計上ヘビーヒッター検出に強く、裾(tail)分布の精密推定には弱いという特性を数学的に説明する。ハッシュ関数はこの保証が有効であるためには対独立(pairwise independence)以上の性質を持たねばならず、実務ではMurmurHash・xxHashのような非暗号ハッシュに異なるシードを与えてd個のハッシュを構成する。
5. 主要な変形と拡張
基本CMSの過大推定を減らすか機能を広げるために複数の変形が提案され、それぞれは「何を諦め何を得るか」が異なる。単に変形を列挙するより、なぜその変形が必要かを理解することが設計判断の核心である。
保守的更新(Conservative Update, CU)は過大推定を実務的に最も大きく減らす手法である。更新時にd個のカウンタをすべて上げる代わりに、まず現在のd個の値のうち最小値mを求め、値がmのカウンタだけをcだけ上げる。問い合わせはどのみち最小値を見るので「すでに十分大きいカウンタ」をさらに大きくしなくても推定に損はなく、代わりに不要な増加が抑えられて平均誤差が大きく減る。代償として削除が不可能になり(負数更新時に保証崩壊)、最小値計算が追加されて更新が少し遅くなる。2024年にも保守的更新の最悪・平均誤差に対する精密分析が発表されるほど、理論的にも依然として活発に研究される変形である。
Count SketchはCMSより先に提案された従兄弟格の構造で、各キーに列インデックスのほかに±1符号ハッシュを追加で付与し、更新時にカウンタに±cを加えたうえ、問い合わせ時にd個の推定の中央値(median)を取る。符号が互いに相殺されて衝突の影響が平均的に0へ収束するので不偏(unbiased)推定となり、誤差がL1(N)ではなくL2ノルムに比例して分布の偏ったストリームでより有利でありうる。また負数更新(削除)を支援する。代わりに符号ハッシュと中央値計算で実装が複雑であり、「決して過小推定しない」というCMSの一方向保証は消える。以下の表は3つの確率的要約の役割の違いを整理したものである。
| 構造 | 答える問い | 誤差方向 | 削除 | 代表指標 |
|---|---|---|---|---|
| [[bloom-filter]] | 所属の有無(あるか?) | 偽陽性のみ | 不可(基本) | FPP |
| [[hyperloglog]] | 一意個数(何種類?) | 両方向 | 不可 | 相対誤差 ~2% |
| Count-Min Sketch | 頻度(何回?) | 過大推定のみ | 不可(基本) | εN, δ |
| Count Sketch | 頻度(何回?) | 両方向(不偏) | 可能 | L2ベース |
このほか可変増加量を対数スケールで圧縮してメモリをさらに減らす変形、時間とともに古い頻度を減衰させる時間減衰(decay) CMS、そしてCMSをウィンドウごとに置いて最近の区間だけを集計するスライディングウィンドウCMSなどがストリーミング分析で広く使われる。どの変形を選んでも「衝突をどう扱うか」という共通の問いに対する異なる答えだという点が核心である。
変形の選択は結局誤差・機能・コストの三角トレードオフである。正確性が最も重要で削除がなければ保守的更新が既定値であり、削除・不偏推定が必要ならCount Sketch、リアルタイムトレンドなら減衰・スライディングウィンドウを載せる形で、要件から逆方向に構造を組み立てる。重要な設計原則は、一度定めた幅・深さ・ハッシュ・符号体系を変えると既存スケッチとのマージ互換性が崩れるという点であり、変形とパラメータはサービスの寿命周期を見据えて慎重に固定せねばならない。
6. 適用事例
ネットワーク監視・DDoS検出がCMSの古典的な活用処である。ルータ・ファイアウォールは毎秒数百万パケットから「異常に多いトラフィックを送る送信元」を見つけねばならないが、すべてのIPごとにカウンタを置くにはメモリが不足する。CMSで送信元IPのパケット数を近似し、閾値を超えるヘビーヒッターだけをACL・[[rate-limiting]]対象に上げれば、数MBのメモリでラインレート検出が可能である。過小推定がないので攻撃トラフィックを見逃す危険がないという点がセキュリティ検出に特に合致する。
データベース問い合わせ最適化も重要な事例である。オプティマイザはジョイン・フィルタの選択度(selectivity)を推定するには列値の頻度分布が必要である。すべての値の正確なヒストグラムを維持するのは高価なので、CMSで特定値の出現頻度を近似し「この条件の結果行数がおよそいくらか」を推定して実行計画を選ぶ。近似でも相対比較には十分であり、メモリ予算が固定されるという点が統計収集のコストを制御してくれる。
キャッシュ置換ポリシーではCaffeineのW-TinyLFUが代表的である。[[caching-strategy]]で見たようにLFUは「よく使われる項目」を保護するには各項目のアクセス頻度を知らねばならないが、数百万キーの正確な頻度表はキャッシュ自体より大きくなりうる。W-TinyLFUはCMSでアクセス頻度を近似し時間減衰を加え、少ないメモリでLRUの新しさとLFUの頻度を結合して高いヒット率を出す。実際CaffeineはGuava比でヒット率・スループットで優位を見せるが、その根幹がCMSベースの頻度推定である。
金融不正・推薦システムでも頻度近似は核心である。カード会社は「短時間に同じ加盟店・端末から異常に多い承認試行が集中するか」をリアルタイムに見ねばならないが、数千万加盟店の正確なカウンタをミリ秒単位で更新・問い合わせするのは難しい。CMSで加盟店・端末・カードBINごとの試行頻度を近似し閾値超過時に追加認証・保留へ回せば、過小推定がないので疑わしい取引を見逃さずに定数メモリで処理される。推薦システムでもアイテム・検索語の人気頻度をCMSで近似して人気補正・重複除去に活用し、正確な数値より相対順位が重要な文脈なので近似誤差が実務上問題にならない。
ストリーミング分析プラットフォームと製品化の面ではRedisが代表的である。Redisの確率的データ構造モジュールはCount-Min Sketchを一級タイプとして提供し、CMS.INITBYDIM(幅・深さを直接指定)またはCMS.INITBYPROB(目標ε・δを指定)でスケッチを作り、CMS.INCRBYで複数項目を一度に更新し、CMS.QUERYで推定頻度を、CMS.MERGEで複数スケッチのマージを支援する。このように「リアルタイム急上昇検索語」「商品別閲覧数の近似」「APIキー別呼び出し量の推定」といったワークロードがアプリケーションコードの修正なしに定数メモリで処理される。大規模分析ライブラリ(例:Spark生態系のスケッチライブラリ)でもCMS・Count Sketch系列が頻出項目推定の基本ツールとして使われる。
7. 深化 — 実務適用時の設計ポイントと最新動向
CMSを実際のシステムに入れる際は理論公式だけで終わらず、運用文脈に合わせた調整が必要である。第一に、ε・δを「望む絶対誤差」から逆算する習慣が重要である。誤差上限がεNなので、ストリーム総量Nが1日に数十億へ大きくなるサービスならεを十分小さく取ってこそ希少キーまで使える推定になる。逆に「上位いくつかのヘビーヒッターだけ分かればよい」ならεを緩く取ってメモリを節約する方が合理的である。すなわち要求精度とメモリ予算のトレードオフをビジネスの問いに合わせて明示的に設計せねばならない。
第二に、減衰とウィンドウ化がほとんど常に必要である。純粋なCMSは累積頻度だけを数えるので「昔の人気」が永遠に残る。急上昇・リアルタイムトレンドを見るには一定周期でスケッチをリセットするか、指数減衰を適用するか、スライディングウィンドウで最近の区間だけを集計せねばならない。これは[[stream-processing-windowing]]の時間意味論と結合する地点で、「何をいつまでの頻度と見るか」を定義する設計決定である。
第三に、過大推定緩和手法の選択である。正確性が重要なら保守的更新(CU)を基本として採択し平均誤差を下げるが、削除が必要なワークロード(例:セッション終了時に差し引き)ならCUの代わりにCount Sketchのように負数更新を支援する構造を使わねばならない。2024年にも保守的更新の誤差特性に対する新たな分析が発表されるなど、CMS系列は「衝突と誤差をより良く飼い慣らす」方向へ着実に発展している。また最近はCMSが頻度推定を学習モデル(learned sketch)と結合し、頻出キーを別の正確カウンタへ抜き希少キーだけをスケッチに任せて全体誤差を下げるハイブリッド設計も研究されている。
第四に、セキュリティ・プライバシーの観点も浮上している。CMSがユーザ行動頻度を集計する際、個別項目を保存しないという性質はプライバシーに友好的だが、衝突による推定だけで機微情報が逆推定される余地もあるため、差分プライバシー(DP)ノイズをスケッチに結合する研究が進行中である。これは「集計の有用性とプライバシー」を同時に扱おうとする最新の流れと接する。
第五に、観測性(observability)と検証を設計に含めねばならない。近似構造は「今の推定がどれだけ外れうるか」が見えなければ信頼しにくい。したがって運用では総量Nと幅wから現在の誤差上限εNを常時計算してダッシュボードに露出し、少数のキーについて正確カウンタと周期的に対照して実際の過大推定幅を監視するのが望ましい。こうして「近似の品質を測定可能な指標へ還元」しておけば、トラフィック特性が変わって誤差が大きくなる際に早めにパラメータを再調整できる。
8. 考慮事項および示唆点
第一に、適用適合性の判断(適用戦略)。 CMSは「頻度/ヘビーヒッターを定数メモリで、過小推定なしに」知りたいとき最適である。逆に正確な頻度表が必要だったり(精算・課金)、一意個数が気になったり([[hyperloglog]])、所属の有無だけ必要なら([[bloom-filter]])別のツールが合う。技術士の観点では「要求が正確性か近似許容か、問いが頻度かカーディナリティか」をまず分解しデータ構造をマッピングする設計力が核心である。
第二に、誤差方向性と安全性設計(トレードオフ)。 CMSの一方向過大推定は「検出で見逃しがない」という安全な失敗(fail-safe)を与えるが、同時に偽警報(false positive)を誘発する。DDoS遮断・不正検出のように誤検知コストが大きい領域では、閾値余裕、二次精密検証、保守的更新を組み合わせて誤検知を制御せねばならない。誤差の方向とコスト構造を一緒に見ることが運用安定性の鍵である。
第三に、分散・ストリーミングアーキテクチャとの整合(連携技術)。 CMSの加法的マージ可能性はMapReduce・Spark・Kafka Streamsのような分散処理と自然に噛み合う。各パーティションがローカルスケッチを作りreduceで加えるパターンはシャッフルコストを無くし、[[stream-processing-windowing]]・減衰と結合してリアルタイムトレンドパイプラインを構成する。データ構造の選択がそのままアーキテクチャのコスト構造へつながるという点を設計初期に反映せねばならない。
第四に、パラメータガバナンスと再現性(運用・展望)。 w・d・ハッシュシード・減衰周期のようなパラメータは一度定めるとマージ互換性のために変えにくい。異なる設定のスケッチは合わせられないので、組織レベルでスケッチ設定を標準化・バージョン管理し、変更時にマイグレーション戦略を置かねばならない。展望としては、学習型スケッチ・差分プライバシー結合・ハードウェア加速(ラインレート処理)でCMSの適用範囲が広がっており、大容量リアルタイム分析の標準要約構造としての価値が持続するであろう。
参考資料
- Cormode, Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications" (2005): http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf
- Redis — Count-Min Sketch 公式ドキュメント: https://redis.io/docs/latest/develop/data-types/probabilistic/count-min-sketch/
- Ben Mazziane, Marfoq, "Count-Min Sketch with Conservative Updates: Worst-Case Analysis" (2024): https://arxiv.org/abs/2405.12034
一言まとめ: Count-Min Sketchはd個のハッシュで2次元カウンタ配列に頻度を重ねて積み、問い合わせ時に最小値を取ることで、一意キー数に依存しない定数メモリで過小推定なしに頻度・ヘビーヒッターを近似する確率的要約構造である。