ブルームフィルタの近似母集団の計算

Question

フィルタのMビット（ここではM < = N）のNビットおよびKハッシュ関数のサイズのブルームフィルタが設定されているとします。

ブルームフィルタに挿入する要素の数を近似することはできますか？

簡単な例

Iは100ビットと10ビットが設定されている5つのハッシュ関数のBFを仮定すると、以下の例にわたって混練してき...

ベストケースのシナリオ：ハッシュ関数が本当に完璧で、いくつかのX個の値に対して一意にマップすると仮定すると、与えられた10ビットが設定されており、BFに2つの要素しか挿入されていないと言える。

最悪シナリオ：ハッシュ関数は悪く、一貫して同じビットにマップされます（まだ私たちは、BFに10個の要素が挿入されたと言うことができます。

この範囲の約数はおそらくフィルタの偽陽性確率によって決まる[2,10]この時点で立ち往生しています。

Answer 1

この質問は、おおよそのストレージの少量の要素の数を概算するためのbetter algorithmsがあるため、少し心配です。

しかし、ブルームフィルタを使用する必要がある場合、ハッシュ関数はランダムまたはアークス（すべての値が独立して選択されているか、または「完全に」完全なハッシュと混同されないように選択されている）と仮定しましょう。今度はボールとビンの問題があります。MのNビンにボールが入っているので、投げたボールの数はいくつですか？スローされるボールの数をBとします。アイテム数はB/Kです。アイテムごとにKボールを投げるためです。

ボールおよびビンプロセスの標準近似は、各ビンを独立したポアソンプロセスとしてモデル化することです。ビンが占有される前の時間は指数関数的に分布する。 1をすべてのボールを投げるのにかかる時間とすると、この指数分布の率の最尤推定値λはPr(Exponential[λ] < 1) = M/Nを満足するので、1 - exp(-λ) = M/Nとλ = -log(1 - M/N)を満たす。パラメータλはボールの数に似ているので、アイテム数の見積もりはB ≈ -N log(1 - M/N)/Kです。

編集：Nビンがあるので、Nを掛ける必要があります。

Answer 2

ハッシュ関数がすべてをランダムにすると仮定すると、Wikipediaというエントリは、特定のビットが設定される可能性の式を提供します。これは1 - (1-1/m)^knです。フィルタにはmビットがあるので、これは、予想される/平均のビット数がm(1-(1-1/m)^kn)になることを意味します。だからnのための合理的にもっともらしい推測を、実際に設定されたビット数に等しくするnを選択することによって思いつくことができます。

このような推測がどれほど正確であるかを知るには、設定されたビット数の分散の考え方が良いでしょう。これを正確に行うことはできますが、それは首に痛みがあります。あなたはVar(X) = E(X^2) - E(X)^2という事実を使うことができます。この場合、E(X^2)は、ビットのペアが両方とも設定される確率に大きく依存します。ビット0が設定され、ビット1がクリアされており、他のすべてのビットがクリアされているなどのステートメントの確率を考慮することで、 「0ビットがクリア」であり、「0および1を除くすべてのビットがクリア」です。