CODEWITHSUNDEEP
bloom-filtercount-min-sketchprobabilistic-ds
aa8y
aa8y

Reputation: 3942

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

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?

Upvotes: 5

Views: 1489

Answers (2)

HollaHieu
HollaHieu

Reputation: 11

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)

Upvotes: -1

roottraveller
roottraveller

Reputation: 8232

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

Upvotes: 0

Related Questions