先日実装した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"
の削除前後で結果がtrue
→false
と変わっていることがわかります。