ブルーム・フィルターに関する質問

ブルームフィルタは、大量のデータ中の有無を検索する問題を解決するために設計されたデータ構造です。

理想的には、nビットのビットマップはn2n個の要素を保持することができます。

ビットマップの長さがmmで、既存のハッシュ関数がkk個あり、入力ドメインの任意の要素に対して、ハッシュによって得られる値は$[0,m]$[0,m]に一様に分布していると仮定します。

$m$現在のフィルタにnn個の要素が挿入されたとき、 k＊nk＊n回の 挿入操作が行われたことになり、どのビットでも0になる確率は $k$k＊nP0＝k＊n、1になる確率は $[0,m]$k＊nP1＝1-k＊nとなります。

$n$この時点で要素が挿入され、ハッシュはk個の位置を取得し、このk個の位置のすべてが既に1であれば、確率 $k\ast n$kP=k＊n)kで偽陽性

Matlabによるグラフ,$P_0=(1-\frac{1}{m}{)}^{k\ast n}$m=k=3,m=0010, nによるP傾向

m=1000の条件下でn=1000の場合、エラー率はすでに80%以上と高く、この場合、最も単純なビットマップに従っても100%正しいことがわかります。ブルームフィルタの利点は何ですか？