ブルームフィルタのパフォーマンス指標：フィルタサイズ・ハッシュ関数数・誤り率の最適バランス

ブルームフィルタにおける3つのパフォーマンス指標

ブルームフィルタには、互いにトレードオフの関係にある3つのパフォーマンス指標が存在します。それは、計算・実行時間(ハッシュ関数の数 k に対応)、フィルタのサイズ(ビット数 m に対応)、そして誤り確率(偽陽性率 f = (1 − p)^k に対応)の3つです。

ブルームフィルタ(BF)は、検索性能と空間効率を高めるために、一定の誤差を許容する設計を採用しています。ブルームフィルタは「true」または「false」のいずれかを返すため、その結果は必ず以下の4つの分類のいずれかに当てはまります。

• 真陽性(True Positive):要素が存在する場合に「true」を返す
• 偽陽性(False Positive):実際には要素が存在しないのに「true」を返す
• 真陰性(True Negative):要素が存在しない場合に「false」を返す
• 偽陰性(False Negative):実際に要素が存在するのに「false」を返す

ブルームフィルタで最も発生しやすいのは偽陽性です。偽陽性・偽陰性のいずれも、システムに余計なオーバーヘッドをもたらします。ブルームフィルタは要素の情報を配列に格納して管理し、その判定結果は確率的に決まるため、「確率的データ構造(probabilistic data structure)」に分類されます。

フィルタサイズとハッシュ関数の数の決め方

フィルタサイズの重要性

ブルームフィルタのサイズが小さすぎると、ビットフィールドがたちまちすべて「1」で埋め尽くされ、どんな入力値に対しても「偽陽性」を返す状態になってしまいます。そのため、フィルタサイズの決定は極めて重要な設計判断となります。フィルタが大きいほど偽陽性は減少し、小さいほど増加します。つまり、ブルームフィルタの適切なサイズは「偽陽性の誤り率」を基準に決定すべきだといえます。

ハッシュ関数の数のトレードオフ

もう一つの重要なパラメータが、使用するハッシュ関数の数です。ハッシュ関数を増やせば増やすほど、ブルームフィルタの処理速度は低下し、フィルタもより早く一杯になってしまいます。逆に数が少なすぎると、今度は多くの偽陽性に悩まされることになります。このバランスを取ることが、高性能なブルームフィルタを実現する鍵となります。

誤り率とパラメータの計算式

偽陽性の誤り率 p は、フィルタサイズ m、ハッシュ関数の数 k、挿入された要素数 n を用いて、次の式で求められます。

p ≈ (1 − e^(−kn/m))^k

実際の設計では、m と k の値をあらかじめ決めておく必要があります。誤りの許容値 p と予想される要素数 n を自分で設定すれば、以下の式からそれぞれのパラメータを算出できます。

m = (−n × ln p) / (ln 2)²

k = (m / n) × ln 2