BloomFilterについて調べてみた
BloomFilterとは
Wikipedia にも記載されていますが、ある要素が集合に属しているかを検査できるフィルタです。
一番最初に思いつく実装としては、こんな感じでしょうか。
- 集合の先頭から順に要素を比較していく
- 途中で見つかれば「属している」
- 最後まで見つからなければ「属していない」
この場合、要素数をNとして、O(N)の計算量が必要ですが、BloomFilterでは、BloomFilterで使用するハッシュ関数の個数をkとして、O(k)で計算ができます。
もちろん、これにはトレードオフがあり、「属している」と判断したものの、
実は「属していなかった」
という偽陽性を許容することで上記のような利点を実現しています。
※ただしBloomFilterでは、原理的に偽陰性はありません。
詳細はこのあとみていきますが、実際に動かしてみるとわかりやすいので、体験したい方はGUIでポチポチできるこちらがおすすめです。
空間効率性
以前、記事
にも書きましたが、A. PaghらによるとBloomFilterにデータを格納するために必要なbit数は [bit]です。
ここで、pを偽陽性確率、Nを集合の要素数とします。
単純に生データを格納することを考えると、要素の大きさ[bit]の領域を確保する必要があります。
例えばユーザIDを8文字英数と絞ったとして [bit]が必要です。このことからもBloomFilterの空間効率性が高いことがわかります。
計算時間
前述の通り、kをBloomFilterで使用するハッシュ関数の個数として、O(k)で計算ができます。 要素の追加もO(k)です。
セキュリティ
副次的なメリットですが、セキュリティ面でも有利な可能性があります。
redis4.0で使えるようになるかもしれないモジュールredabloomsでも使われているDebloom。
こちらのREADMEを読むまで発想すらなかったですが、アプリケーションでの応用を考えたときに実データを保持しなくてよいというセキュリティ上のメリットも考えられます。
READMEにあるのは以下の記載なので、そこまで踏み込んだ記載ではないですが……。
A Bloom filter gives the application cheap, memory efficient set operations, with no actual data stored about the given element.
どういうことかと言うと、BloomFilterでは実データのハッシュを計算し、その結果をもとに配列へのマッピングを行うため、実データそのものをストアしておく必要がありません。
当然、この場合は暗号学的な現像計算困難性や衝突困難性を満たすようなハッシュ関数を選択する必要があります。
MD5のようなハッシュ関数を使用している場合は、この限りではありません。
応用先
Broderらのsurveyによると1970年にBloomによって提案されて以来、初期のUNIXのスペルチェックで使われていたそうで、今でもデータベースの分野でよく使われているそうです。
セキュリティ の箇所でも述べましたが、 redis にも以下の記載があり、使われているようです。
Encode a lot of data in little space, or create a Redis backed Bloom Filter using GETBIT and SETBIT.
Broderらのsurveyでも述べられていますが、リストで持つようなデータではBloomFilterに応用できる可能性があるということの実例ですね(リストで保持している=検索したいという考えのもとで)。
ほかにもsquid-cache
でも使われていたり、http2のcache-aware server pushの文脈でもBloomFilterが登場します。cache-aware server pushでは、Golomb coded setが使われているみたいです。
Golomb coded setについては以前まとめたのでこちらをどうぞ。
最後に
応用先について、調べれば調べるほど出てきてまだまだ出てきそうです。読んでいる途中の論文でも登場しているので、まとまったら追記したいです。
実装もそのうち記事にします。。。
2017/2/4 追記
実装も記事にしました。
参考
- C++でブルームフィルタを実装する方法
- ブルームフィルタ - Wikipedia
- Bloom Filters by Example
- Double hashing
- Debloom
- A. Pagh, R. Pagh, and S. S. Rao. An optimal bloom filter replacement. In Proc. ASM-SIAM Symposium on Discrete Algorithms, SODA, 2005.
- Broder, Andrei, and Michael Mitzenmacher. “Network applications of bloom filters: A survey.” Internet mathematics 1.4 (2004): 485-509.
- redablooms
- Redis 4.0 RC1 出たし、Redis モジュールを紹介してみる HTTP/2の課題と将来
- squid-cache wiki