Comment on Bloom filters: real-world applications
noli@programming.dev 1 year agoInteresting. Do I understand it correctly if I say it’s a bloom filter where instead of setting a bit to 1 for each of the hashes, you increment a counter for that hash?
How do you infer the count then, take the minimum of all matching hashes? Because intuitively it seems to me like you would need a lot more space to avoid counts being too high
Reader9@programming.dev 1 year ago
This data structure uses a 2-dimensional array to store data, documented in this scala implementation: github.com/twitter/…/CountMinSketch.scala. I’m still trying to understand it as well.
Similar to your idea, I had thought that by using k bloom filters, each with their own hash function and bit array, one could store an approximate count up to k for each key, which also might be wasteful or a naïve solution.