ブルームフィルタ
2004年、Bernard Chazelle、Joe Killian、Ronitt Rubinfeld、Ayellet Tal はブルームフィルタに追加した要素と関連させた値を持つ連想配列を設計した。ブルームフィルタと同様、このデータ構造も空間効率が良く、偽陽性発生の可能性がある。Bloomier filter での偽陽性は、キー値がマッピングされていないのに値が返される場合である。ただしマッピングされているキー値に対しては不正な値を返すことはない。
単純な Bloomier filter でその動作を説明しよう。まず取り得る値が 0 と 1 だけの連想配列を考える。2つのブルームフィルタ A0 と B0 を作成する。そうして値が 0 であるキーは A0 に登録し、値が 0 であるキーはB0 に登録する。あるキーに対応する値を求めるときには、両方のフィルタを参照する。もしどちらにもそのキーがない場合には、そのキーとそれに対応する値はない。キーが A0 にあって B0 にない場合には、そのキーに対応する値は 1 ではなくて、高い確率で 0 であると言える。逆にキーが B0 にあって A0 になければ、キーに対応する値は 0 ではなくて、高い確率で 1 であると言える。
偽陽性のリスクはあるが、ブルームフィルタは同様の集合的データ構造(平衡2分探索木、trie、ハッシュテーブル、単純な配列、線形リスト)に比べると遥かに空間効率が良い。それらのほとんどはどれも少なくとも要素のデータ自体を保持する必要があり、要素データが小さな整数ならば少なくて済むが、文字列のように任意長のデータであればそれなりのメモリ領域を必要とする(trie は例外である。trie ではたとえば文字列の同じ位置が同じ文字であればそれを共有することができる)。リンクを持つデータ構造はポインタを格納するための追加のメモリ領域を必要とする。これに対して、誤り率 1% で k の値が最適化されているブルームフィルタであれば、1要素当たり 9.6 ビットの格納領域があればよい。これは要素のデータそのもののサイズとは無関係な値である。この利点は配列を利用している点と確率的特徴から生じている。1% の偽陽性率が高いという場合には、要素ごとに 4.8 ビットの領域を追加するごとに、誤り率をさらに 10分の1 にできる。
しかし、取りうる要素の種類が少なく、その多くが集合に含まれている場合には、ブルームフィルタよりも確定的なビット配列の方が効率が良い。確定的なビット配列では、取りうる要素あたり1ビットにより表すことができるのだから。