固定偽陽性確率を持つ圧縮ブルームフィルタ

Question

このペーパーCompressed Bloom Filters by Michael Mitzenmacherに従って圧縮ブルームフィルタの実装を実装しようとしています。私は計算する必要がありますm - ビット数とk - 一定の固定偽陽性確率のハッシュ関数の数。例えば： 私はN = 1000要素（ブルームフィルタに挿入される）と、所与の確率P = 0.01を持っている場合、ビットの「最適な」数は、ブルームフィルタの(-n * Math.log(p)/(Math.log(2) * Math.log(2))) = 9585 であろうことがわかっていますまた、私はk =（9585/1000）* Math.log（2）= 7 - ハッシュ関数が必要です。つまり、私は偽陽性率0.01を取得します。 ブルームフィルタを「圧縮」するには、より疎なフィルタを構築する必要があります。ハッシュ関数が少なく、ベクトルのビット数が増えます。 しかし、この疎なフィルタのハッシュ関数の数とビット数を計算する方法を知りませんでした。 kを1減らすと、ビット数はどのように増加しますか？比率は何ですか？

Answer 1

まあ、私は、ハッシュ関数の数と固定偽陽性率を持つビットの数の間に具体的な比は見つかりませんでした。しかし、私はそのような値の事前計算テーブルを見つけました。 Hereハッシュ関数の数と対応する偽陽性率を持つビットベクトル長さの値を見つけることができます。このような表があるので、ハッシュ関数の数（最適よりも少ない）および偽陽性率が与えられたものと等しいかそれより小さい対応するビットベクトル長を見つけることができる。 Hereは、「疎」ブルームフィルタを構築するための実装です。 これは将来誰かの時間を節約したいと考えています。