例えばデータストアへのアクセス抑制のためにキーの存在を確認する際、 全てのキーを保持して探索すれば100%正しく判定できるが、キーが長く数が膨大になるとメモリの使用量が問題になることがある。 もし偽陽性が許容できるなら、次のフィルタを使うことで空間効率良くキーの存在を確認できる。
Bloom filter
1970年に考案されたフィルタで、 LevelDBやCassandraで使われている。
GoogleのkvsライブラリLevelDBを使う - sambaiz-net
初期値0のビット配列と、そのいずれかのビットにデータをマッピングするk個のハッシュ関数を定義し、 含めるデータを各ハッシュ関数に通して、マッピングされたビットを1に更新していく。 これにより、いずれかのハッシュ関数によって0のビットにマッピングされるデータは、必ずフィルタに含まれないことが分かる。 また、ビット配列のANDを取れば和集合のフィルタになる。
データの追加と存在の確認を、いずれも要素数に依存しないO(k)で行うことができるが、削除はできない。
0/1ではなくインクリメントしていくCounting filterという実装にすると空間効率は劣るが、デクリメントすることで削除できるようになる。
偽陽性率はビット配列長を大きくすると低くなり、データの数が増えると高くなる。 kはビット配列の情報量を最大化させる、つまり半分のビットが1になるように最適化する。
自己情報量、エントロピー、KL情報量、交差エントロピーと尤度関数 - sambaiz-net
Goのwillf/bloomで作成したBloom filterにデータを追加し存在を確認しているのが次のコード。 ハッシュ関数にはpybloomfiltermmap3などと同じくMurmurHash3が用いられている。
package main
import (
"encoding/binary"
"fmt"
"io"
"sync"
"github.com/willf/bitset"
"github.com/willf/bloom"
)
func bits(filter *bloom.BloomFilter) []uint64 {
r, w := io.Pipe()
ret := []uint64{}
wg := &sync.WaitGroup{}
wg.Add(1)
go func() {
var m, k uint64
if err := binary.Read(r, binary.BigEndian, &m); err != nil {
panic(err)
}
if err := binary.Read(r, binary.BigEndian, &k); err != nil {
panic(err)
}
b := &bitset.BitSet{}
if _, err := b.ReadFrom(r); err != nil {
panic(err)
}
ret = b.Bytes()
wg.Done()
}()
filter.WriteTo(w)
w.Close()
wg.Wait()
return ret
}
func main() {
filter := bloom.New(20, 4)
fmt.Printf("%020b\n", bits(filter)) // => [00000000000000000000]
filter.Add([]byte("Foo"))
fmt.Printf("%020b\n", bits(filter)) // => [00000000010001001010]
filter.Add([]byte("Bar"))
fmt.Printf("%020b\n", bits(filter)) // => [00000000110011001010]
fmt.Println(filter.Test([]byte("Foo"))) // => true
fmt.Println(filter.Test([]byte("Hoge"))) // => false
fmt.Println(filter.EstimateFalsePositiveRate(10)) // => 0.52551
}
Goのio packageのReader/Writer/Closer/Seeker interfaceとストリーム処理 - sambaiz-net
Cuckoo filter
2014年に発表されたフィルタ。
Cuckoo Filter: Practically Better Than Bloom
データを追加する際は、そのままハッシュ関数に通したi_1と、フィンガープリントfをハッシュ関数に通したものとi_1のXORであるi_2を取って、
対応するいずれかのバケットが空いていたらそこにfを入れる。
いずれも空いていなければ、そのどちらかから一つ追い出して、その値とindexのXORを取れば分かるもう片方のバケットに再度入れる。
既にそこも一杯ならそこからも追い出し、同様の処理を行う。これを追い出されなくなるまで繰り返す。
そして、もしfがいずれのバケットにも入っていない場合、キーが存在しないことが分かる。それをバケットから除けば削除される。
バケットの空きが十分ならCounting filterよりも高速にデータを追加できるが、埋まるに連れて追い出しが頻発しパフォーマンスが下がっていく。
フィンガープリントを長くすると、Bloom Filterと比較して少ない容量で偽陽性率を低くできる。