Golangでcounting BloomFilterを実装してみた

先日実装したBloomFilter に要素の削除ができるようにcounting BloomFilterを実装しました。

概要

単純なBloomFilter では要素を削除することはできません。
BloomFilterへのマッピングが、削除したい特定の要素によるものか、はたまた別の要素によるものか区別することができないためです。

counting BloomFilterでは、BloomFilterにDelete()ができるようにマッピングbooleanからcountingができるようmulti-bit化しています。
当然、その分空間効率性が犠牲になります。Fanらのpaper のイントロによると、一般的には3-4[bit]で実装するそうなので、3-4倍空間効率が悪くなります。
今回はGolangのprimitive型であるuint8を使用したため、アイデア自体は変わらないですが、一般的なcounting BloomFilterよりも空間効率が劣ります。

実装と結果

gistb38c96069b177b4f64ede336c658b976

要素"2"の削除前後で結果がtruefalseと変わっていることがわかります。

参考