Why are bloom filters not implemented like count-min sketch?

Question

So I only recently learned about these, but from what I understood counting bloom filters are very similar to count-min sketches. The difference being that the former use a single array for all hash functions and the latter use an array per hash function.

If using separate arrays for each hash function will result in less collisions and reduce false positives, why are counting bloom filters not implemented as such?

Answer 1

Though both are space-efficient probabilistic data structures, BloomFilter and Count-min-sketch solve diff use-cases.

• BloomFilter is used to test whether an element is a member of a set or not. and It gives boolean False positive results. False positive means, it might tell that a given element is already present but actually, it’s not. See here for working details: https://www.geeksforgeeks.org/bloom-filters-introduction-and-python-implementation/
• Count-min-sketch tells about keeping track of the count of things i.e, How many times an element is present in a set. See here for working details: https://www.geeksforgeeks.org/count-min-sketch-in-java-with-examples/

Answer 2

I would like to add to @roottraveller answer and try to answer the OP question. First, I find the following resources really helpful for understanding the basic difference between Bloom Filter, Counting Bloom Filter and Count-min Sketch: https://octo.vmware.com/bloom-filter/

As can be find the document:

• Bloom Filter is used to test whether an element is a member of a set or not
• Count-min-sketch is a probabilistic data structure that serves as a frequency table of events in a stream of data
• Counting Bloom Filter an extension of the Bloom filter that allows deletion of elements by storing the frequency of occurrence

So, in short, Counting Bloom Filter only supports deletion of elements and cannot return the frequency of elements. Only CM sketch can return the frequency of elements. And, to answer OP question, sketches are a family of probabilistic data structures that deals with data stream with efficient space time complexity and they have always been constructed using an array per hash function. (https://www.sciencedirect.com/science/article/abs/pii/S0196677403001913)