在「Cuckoo Filter implementation in Go, better than Bloom Filters」這邊看到這個資料結構,有興趣的人也可以看「Cuckoo Filter:设计与实现」這篇介紹,下面是我抓重點整理。
Bloom Filter 支援的操作:
Add(element)
Query(element)
1970 年提出來的資料結構。優點是空間複雜度是 O(1),Query(element)
會有可接受的 false positive,缺點是不支援 Delete(element)
、以及數量變多時誤判率的增加。
Cuckoo Filter 多了一組操作:
Delete(element)
2014 年提出來的資料結構。空間複雜度一樣是 O(1),但相同的空間用量下 false positive 變低,然後支援 Delete(element)
了。也因此論文直接寫「Cuckoo Filter: Practically Better Than Bloom」,表示可以直接替代。
2 thoughts on “Cuckoo Filter:比 Bloom Filter 多了 Delete”