パフォーマンスメトリクス

ブルームフィルターには、計算時間または実行時間（ハッシュ関数の数kに対応）、フィルターのサイズ（ビット数mに対応）、エラーの確率（に対応）の3つのパフォーマンスメトリックがあります。偽陽性率

f =（1 − p）k）

ブルームフィルター（BF）は、ルックアップパフォーマンスとスペース効率を向上させるためのエラートレランスを導入します。ブルームフィルターはtrueまたはfalseを返します。したがって、ブルームフィルターの結果は、真陽性、偽陽性、真陰性、および偽陰性のいずれかのクラスに分類されます。ブルームフィルターに含まれる誤検知の最大数。誤検知と誤検知は、システムにオーバーヘッドを引き起こします。ブルームフィルターは、要素の情報を格納するための配列を実装します。誤検知は次のように定義されます。要素を保持しているときにブルームフィルターがtrueを返す場合。同様に、フォールスネガティブも次のように定義されます。ブルームフィルターは、要素を保持するとfalseを返します。したがって、ブルームフィルターは確率的データ構造に属します。

ブルームフィルターのサイズとハッシュ関数の数

ブルームフィルターのサイズが小さすぎると、すぐにすべてのビットフィールドが「1」になり、入力されたすべての値に対してブルームフィルターが「誤検知」を返すことを理解しています。したがって、ブルームフィルターのサイズは、非常に重要または重要な決定を下す必要があります。大きなフィルターは誤検知が少なく、小さなフィルターはより多く構成されています。

したがって、ブルームフィルターのサイズは完全に「誤検知エラー率」に基づいていると結論付けることができます。

もう1つの重要なパラメーターは、使用するハッシュ関数の量を決定することです。実装するハッシュ関数が多いほど、ブルームフィルターは遅くなり、いっぱいになるのも早くなります。ただし、数が少なすぎると、誤検知が多く発生する可能性があります。

次の式を使用して、フィルターのサイズm、ハッシュ関数の数k、挿入された要素の数nに基づいて、誤検出エラー率pを計算できます。

p≈（1-e ^{（-kn / m）} ） ^k

実際には、ほとんどの場合、mとkがどうなるかを決定する必要があります。したがって、エラー許容値pと要素数nを自分で設定または修正すると、次の式を実装してこれらのパラメータを計算できます

m =（-n ln p）/（ln 2） ²

k =（m / n）*（ln 2）