確率的スケッチの容量・推定誤差

ストリームの異なり数または非負更新の頻度推定に必要な配列容量と理論誤差の確認。

入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。

選択内容に応じて、残りの入力項目を案内します。

計算する内容

推定対象の異なり数。0以上の整数を入力。

漸近RSEの目標値。信頼水準ではありません。


計算結果

必要な値を入力すると自動で計算します。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

HLL: m=2^p、RSE≈1.04/√m。目標RSE以下の最小整数pを7~24から選びます。64ビットハッシュと6ビット詰めまたは8ビット格納で、配列容量B=ceil(m×レジスタ幅/8)。CMS: w=ceil(e/ε)、d=ceil(ln(1/δ))。逆算時はε=e/w、δ=exp(−d)。誤差は真の頻度に加えてεN以下となる確率が少なくとも1−δです。容量B=w×d×カウンタ幅/8。CMSの保証は非負更新、独立したハッシュ関数、カウンタ非飽和が条件です。

配列メモリB・KiB、HLLの漸近RSE、CMSの片側加算誤差と成功確率、配列寸法と内訳。

計算例(架空の数値)

HLLで目標1%、64ビットハッシュ、6ビット/レジスタならp=14、m=16384、相対標準誤差0.8125%、配列容量12288 B。CMSでN=1000000、ε=0.1%、成功確率99%、32ビットカウンタならw=2719、d=5、全13595カウンタ、54380 B。

適用対象と限界

64bit一様ハッシュによる異なり数の概算設計、または非負整数更新のCount-Min Sketch単一キー頻度問い合わせ。Bloom filterの会員判定、HLL++の疎表現・バイアス補正、ハッシュ関数実装・実測精度、負の更新、連続更新でのカウンタ飽和、配列外メモリの見積もりには対応しません。。

方法と出典

方法:Flajolet et al. (2007) HLL;Heule et al. (2013) 64-bit registers;Cormode & Muthukrishnan (2005) CMS。データ記録日:2026-11-13。