Scalable Bloom Filtersとは一体....？ #アルゴリズム

Wikipediaを漁っていたところScalable Bloom Filters(SBF)というデータ構造を発見してしまったので紹介します¹。

参照した論文

http://haslab.uminho.pt/cbm/publications/scalable-bloom-filters

Bloom Filter

SBFの説明に入る前に、Bloom Filterについて簡単に紹介します。もっとも、日本語のWikipediaでも十分詳しい説明が載っていたりするのですが……。

ささっと説明

Bloom Filterはちょっと不思議な性質を持つデータ構造の一種です²。

いわゆるSetと同じ操作を提供する
- 要素を入れる操作と、ある要素が入っているかを調べる操作
- どちらも時間計算量O(1)で実現できる
ハッシュテーブルなどを用いて実装される同種のデータ型と比して、とても空間効率が良い
その代わりに、ある要素が入っているかの判定を一定確率で間違える
- 入れたことがない要素に入っていると判定してしまう（偽陽性）
- 逆（偽陰性）は起こらない
間違える確率は、いくつかのパラメータ（入れる要素数・使うメモリの大きさ・ハッシュ関数の個数）によって定まる（トレードオフの関係の中でコントロールできる）

上述の特性は、要素を追加するときに「mビットの領域を用意し、追加する要素をk個のハッシュ関数に通して0〜m-1の範囲の値を得て、値をビット領域に対する添字とみなし、対応するビットを立てる」ことで実現されます。逆に要素が入っているか調べるには、「同様にk個のハッシュ値を計算し、それぞれが示すビットが全て立っているか」で判定します。

何やらややこしい説明をしてしまいましたが、実装を見たほうが分かりやすいです。

ささっと実装

Rubyによるナイーブな実装だとこんな感じでしょうか³。

bloom_filter.rb

class BloomFilter
  def initialize(m, k)
    @bits = Array.new(m).fill(0)
    @m, @k = m, k
  end

  def add(e)
    # k個のハッシュ値を計算して、その値のビットを立てる
    @k.times do |i|
      value = [e, i].hash % @m
      @bits[value] = 1
    end
    nil
  end

  def include?(e)
    # k個のハッシュ値を計算して、その値のビットが全て立っているかを調べる
    @k.times do |i|
      value = [e, i].hash % @m
      return false if @bits[value] == 0
    end
    true
  end
end

実行例です。"a"は入れたものが含まれていると正しく判定され、"c"は入れていないので含まれていないと正しく判定されています。一方で"k"は偽陽性の例になっています。

>> b = BloomFilter.new(10, 3)
=> #<BloomFilter:0x007ff6650e4e40 @bits=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], @m=10, @k=3>
>> b.add("a")
=> nil
>> b.add("b")
=> nil
>> b
=> #<BloomFilter:0x007ff6650e4e40 @bits=[0, 1, 1, 1, 0, 0, 0, 0, 1, 1], @m=10, @k=3>
>> b.include?("a")
=> true
>> b.include?("c")
=> false
>> b.include?("k")
=> true

各パラメータの関係

Bloom Filterを利用する際には、パラメータとしてフィルタサイズmとハッシュ関数の個数kを事前に決めなければなりません。さらに、要素が追加される個数nにも偽陽性率は関係してきます。

mが大きくなればなるほど偽陽性の確率は下がる
nが大きくなればなるほど偽陽性の確率は上がる
m, nから最適なkは計算できる

スライス

SBFで利用するのは通常のBloom Filterとは少し違う、スライスによってフィルタが分割された形式のBloom Filterです。

全体としてフィルタのサイズは $M$ ビット
フィルタは $k$ 個のスライスによって分割されている
- 各スライスは $m = M / k$ ビット
$k$ 個のハッシュ関数を $h_1, h_2, ..., h_k$ と書くとき、各ハッシュは $0 \le h < m$ の間で値をとる
各スライスに1つのハッシュ関数が割り当てられ、要素の追加時にはハッシュの計算後、対応するスライスのビットを立てるようにする

このとき、次のことが分かります⁴。

フィルタサイズ $M$ と偽陽性率の閾値 $P$ から、最適な（もっとも多くの要素を追加できる、効率の良い）スライスの数 $k$ を求めることができる
- $k = \log_2 \frac{1}{P}$ のとき最適となる

Scalable Bloom Filters

やっと本題です。Bloom Filterには前述のような制約がありました。

偽陽性率を閾値以下にするためには、要素追加数 $n$ を事前に想定した上でフィルタサイズを決めなければならない
- もし $n$ 以上の要素を追加することになってしまった場合は、偽陽性率を上げざるを得ない
- かといって十分に大きい $n$ を想定すると、フィルタサイズが大きくなりすぎて空間効率が損なわれる

SBFは、偽陽性率をコントロールしながら要素追加に対応できるBloom Filterを実現します。

アルゴリズムのアイディア

SBFの基本的な考えは「今のBloom Filterが一杯になったら、別のBloom Filterを動的に追加して、そちらに要素追加を行う」というものです。

SBFは初期状態として、1つのBloom Filterを持ち、それに要素追加をしていく
- 各Bloom Filterは上述のスライスを用いた形式のもの
Bloom Filterが一杯になった⁵ら、新たにBloom Filterを生成し、そちらに要素追加を行うようにする
ある要素がSBFに含まれているかは、SBFが持つ全てのBloom Filterのうちいずれかで、含まれていると判定されるかで定まる

複数のBloom Filterの全てで判定をするため、偽陽性率を変えないままのBloom Filterを単純に増やすだけだと、偽陽性率が上がってしまいます。また、SBFは少数要素が追加される場合から大量の要素を含む場合まで、さまざまなケースに対応させたいという要求があります。

そこで次のようなルールを導入します。

新しく追加されるBloom Filterの偽陽性率は、直前のBloom Filterの偽陽性率に $r$ を掛けたものにする
- 最初のBloom Filterの偽陽性率を $P_0$ とすると、順に $P_0, P_0r, P_0r^2, \cdots$ となる
- $0 < r < 1$ を満たすように $r$ を選ぶ。後から追加されるBloom Filterほど、偽陽性率が厳しくなる
新しく追加されるBloom Filterのフィルタサイズは、直前のBloom Filterのフィルタサイズに $s$ を掛けたものにする
- 最初のBloom Filterのフィルタサイズを $m_0$ とすると、順に $m_0, m_0s, m_0s^2, \cdots$ となる

SBFとして実現したい偽陽性率を $P$ とするとき、次の関係があることが分かります⁶。ここで $k_i$ は $i$ 番目のフィルタのスライス数を指します。

$P \le P_0 \frac{1}{1-r}$
$k_0 = \log_2P^{-1}_0$
$k_i = k_0 + i \log_2 r^{-1}$

※ $r = 1/2$ を選択すると、数式が全体的に簡略化されて捗るっぽいです

ここまででやっと $P$ から実装に必要な値を計算できるようになりました。

実装

まずはスライスを持つBloom Filterを実装します。今までとインタフェース的に異なるのは、容量の上限をnで受け取るようになったことと、カウンタが実装されたこと、それに伴って#full?が用意されたことです。

slice_bloom_filter.rb

class BloomFilter
  def initialize(m, k, n)
    @bits = Array.new(m).fill(0)
    @k, @n = k, n
    @slice_size = m / k
    @count = 0
  end

  def add(e)
    @k.times do |i|
      value = [e, i].hash % @slice_size
      @bits[@slice_size * i + value] = 1
    end
    @count += 1
    nil
  end

  def include?(e)
    @k.times do |i|
      value = [e, i].hash % @slice_size
      return false if @bits[@slice_size * i + value] == 0
    end
    true
  end

  def full?
    @count >= @n
  end
end

次にSBF本体を実装します。お手軽ですね！！

scalable_bloom_filters.rb

class ScalableBloomFilters
  def initialize(prob, r: 1/2r, s: 2)
    @prob = prob * (1 - r) # P0
    @r, @s = r, s
    @m = 128 # m0
    @k = @k0 = Math.log2(@prob ** -1).ceil
    @filters = []
    append_filter
  end

  def add(e)
    append_filter if @filters.last.full?
    @filters.last.add(e)
  end

  def include?(e)
    @filters.any? {|filter| filter.include?(e) }
  end

  private
  def calc_capacity(m, prob)
    denomi = m * (Math.log(2)) ** 2
    numer = Math.log(prob).abs
    (denomi / numer).floor
  end

  def append_filter
    @filters << BloomFilter.new(@m, @k, calc_capacity(@m, @prob))
    i = @filters.size # iは次のフィルタで使う値であることに注意。-1しなくてもよい
    @prob = @prob * @r
    @m = (@m * @s).to_i
    @k = (@k0 + i * Math.log2(@r ** -1)).ceil
    nil
  end
end

ちなみに、この実装が正しいのか簡単にテストしてみたのですが、偽陽性率が思ったより高そう……と思いきや、どうも#hashの使い方が雑すぎるっぽいです。とりあえずハッシュ計算部分をMD5に取り替えてみたところ怪しくないぐらいの様子になりました。

パラメータの選択

SBFはいくつかパラメータを持っていますが、その値をどう選ぶかは一つの問題になります。元論文では

$r$ は $r=1/2$ が自然だが、実験的には0.8〜0.9ぐらいが割とよさそう
$s$ は利用シナリオ次第だが、2, 4ぐらいがよさそう

としています。初期フィルタサイズである $m_0$ について言及がないのですが、論文中の評価では $m_0=128$ が使われています。今回の実装でも128を使うようにしました。

まとめ

Scalable Bloom Filtersというデータ構造があるらしい！！
- 追加する要素数を事前に決めなくても、勝手に大きくなってくれるBloom Filterだった
Rubyでお手軽に実装してみました

Appendix

数式を追う辺りをもうちょっと詳しく書きます。論文に書いてない説明も適当に補います。幸いなことに、出てくる数学的な処理は高校数学ぐらいでなんとか理解できる範囲です。

充填率

スライスの充填率(fill ratio)を「スライス内で立っているビットが、 $m$ ビットのうちどれだけあるかの割合」で定義します。

各スライスの各ビットについて、1回の要素追加でビットが立つ確率は$1/m$
したがって$n$要素が追加されたときに、0である確率は$(1-1/m)^n$
- 逆に、立っている確率 $p$ は $1-(1-1/m)^n$

ここでいう $p$ は各ビットについて立っているかどうかの確率ですが、スライス内部の各ビットについて確率 $p$ で立っているため、充填率もまた $p$ となります。

大事なことですが $P$ とは $P = p^k$ の関係があります。

最も効率のいいスライスのパラメータ

やりたいのは、ある偽陽性率$P$とフィルタサイズ $M$ が与えられているときに、最もたくさん要素を保持できるようにパラメータ$k, m$を選ぶことです。

上記のように $p = 1-(1-1/m)^n$
$m$は通常、十分大きいので、テイラー展開を用いた近似式$e^{(-1/m)} = 1 - \frac{1}{m} + \cdots \approx 1-\frac{1}{m}$が適用できる
まとめると $p \approx 1-e^{-n/m}$ であり $n \approx -m \ln (1-p)$ でもある
もっと頑張ると $n \approx M \frac{\ln p \ln(1-p)}{-\ln P}$
- $m = M/k$ だったことと、 $P = p^k$ を利用して式変形している

$M, P$ は定数なので、 $n$ を最大化させるような $p$ を見つける問題を解きます⁷。

$n$ が最大となるのは $p=1/2$ のとき
- そのとき $n \approx M \frac{(\ln 2)^2}{|\ln P|}$ となる ⁸
また $P=p^k$ より $k = \log_2 \frac{1}{P}$

これによってフィルタサイズと偽陽性率から、最適なスライスサイズを求めることができるようになりました。

数列の辺りの数式処理

まず、 $P \le P_0 \frac{1}{1-r}$ についてです。

$P$ はどれかのフィルタにひっかかる確率なので$P=1-\prod^{l-1}_{i=0} (1-P_0r^i)$です（$l$ はSBFが持つフィルタの数）。これを出発点に評価していきます
$ 1-\prod^{l-1}_{i=0} (1-P_0) \le \sum_i P_i $ という式が知られている⁹のでこれを用いる

すると

P \le \sum^{i-1}_{i=0}P_0 r^{i} \le \lim_{l \rightarrow \infty} \sum^{l-1}_{i=0} P_0 r^i = P_0 \frac{1}{1-r}

というわけで

P \le P_0 \frac{1}{1-r}

が得られます。最後の変形はいわゆる等比数列の総和の公式っぽいですね。

次に $k_0 = \log_2 P_0^{-1}$ ですが、これはスライスの箇所の議論で登場した $k = \log_2 \frac{1}{P}$ そのままです。

最後に$k_i = k_0 + i \log_2 r^{-1}$ ですが、$P_i = P_0 r^i$ だったので

k_i = \log_2 P_i^{-1} = \log_2 (P_0 r^i)^{-1} = \log_2 P_0^{-1} + \log_2 r^{-i} = k_0 + i \log_2 r^{-1}

という感じです。

こういったデータ構造に詳しいわけではないです……本当にたまたま見つけただけです。 ↩
確率的データ構造というらしいです。 ↩
ビット扱うのが面倒なのでArrayで代用したのと、k個のハッシュを作るのが面倒だったので、0〜k-1それぞれについて要素として含まれる配列を作って#hashを呼ぶことで、お手軽にk個のハッシュ値を生成しています。実用的な実装であれば、k個のハッシュ関数を作るにはダブルハッシュ法を使うなどの工夫をするべきなようです。参考: https://postd.cc/how-to-write-a-bloom-filter-cpp/ ↩
ちゃんとした証明は論文に書いてあります。さすがにそれを全部説明し直すのは大変だったので……できるかぎりAppendixには書きました。 ↩
一杯になったというのは、事前に指定されたフィルタサイズと偽陽性率から計算された、追加可能な $n$ 要素を追加しきってしまったときを指します。 ↩
これもやっぱり分からないので、Appendixのほうに説明を書きます。 ↩
本当は微分して〜とかになるはずが、さらに記述が長くなってしまうので、Wolfram先生の力を借りたい。 http://wolfr.am/9g2IIgzw ↩
これは元論文と同じ形の式なのですが、さらっと $-\ln P = |\ln P|$ としてあります。 $P < 1 < e$ なので $\ln P < 0$ に注意してください。そこからさらに符号を反転して……だと分かりづらいので、絶対値だけを付けておくほうが式として簡潔だろうという判断があるのだと思います。 ↩
一見して謎の関係ですが、 $0 \le P_i \le 1$に注意しながら数学的帰納法を使えば証明できます。確率論とかでは比較的有名な式っぽいですが知らなかった……。 ↩