サイズが N ビットのブルーム フィルターと K 個のハッシュ関数があり、そのうちの M ビット (M <= N) のフィルターが設定されます。
ブルーム フィルターに挿入される要素の数を概算することは可能ですか?
簡単な例
私は、100ビットのBFと10ビットが設定されている5つのハッシュ関数を想定して、次の例を熟考してきました...
最良のシナリオ: ハッシュ関数が本当に完璧で、いくつかの X 個の値に対してビットを一意にマップすると仮定すると、10 ビットが設定されているとすると、BF に挿入された要素は 2 つだけであると言えます。
最悪のシナリオ: ハッシュ関数が正しくなく、一貫して同じビットにマップされている (ただし、互いに一意である) と仮定すると、10 個の要素が BF に挿入されたと言えます。
範囲は [2,10] のようです。この範囲の約は、おそらくフィルターの偽陽性確率によって決定されます。この時点で立ち往生しています。
少量のストレージで個別の要素の数を概算するためのより良いアルゴリズムがあるため、この質問は少し心配です。
それにもかかわらず、ブルーム フィルターを使用する必要がある場合は、ハッシュ関数がランダムなオラクルであると仮定しましょう (完全なハッシュと混同しないように、個別に選択されたすべての値、または「本当に完全な」)。ここで、ボールとビンの問題があります。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ます。
ウィキペディアのエントリは、ハッシュ関数がすべてをランダムにすると仮定して、特定のビットが設定される確率の公式を示しています。これは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クリア」です。