確率的スケッチの容量・推定誤差
バグ・不具合を報告
ストリームの異なり数または非負更新の頻度推定に必要な配列容量と理論誤差の確認。
入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。
選択内容に応じて、残りの入力項目を案内します。
計算結果
—B
- 配列の容量
- —KiB
- 理論誤差指標
- —
- 想定件数での誤差目安・上限
- —
- 確率条件
- —
- 配列寸法
- —
必要な値を入力すると自動で計算します。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
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。