this post was submitted on 06 Sep 2023
32 points (97.1% liked)

Programming

17484 readers
162 users here now

Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!

Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.

Hope you enjoy the instance!

Rules

Rules

  • Follow the programming.dev instance rules
  • Keep content related to programming in some way
  • If you're posting long videos try to add in some form of tldr for those who don't want to watch videos

Wormhole

Follow the wormhole through a path of communities [email protected]

founded 1 year ago
MODERATORS
snowe
Ategon
[email protected]
32
Bloom filters: real-world applications (llimllib.github.io)
submitted 1 year ago by Reader9 to c/programming
10 comments fedilink hide all child comments
 

What are your real-world applications of this versatile data structure?

They are useful for optimization in databases like sqlite and query engines like apache spark. Application developers can use them as concise representations of user data for filtering previously seen items.

The linked site gives a short introduction to bloom filters along with some links to further reading:

A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set.

you are viewing a single comment's thread
view the rest of the comments
[–] noli 2 points 1 year ago (1 children)

Interesting. 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 2 points 1 year ago* (last edited 1 year ago)

This data structure uses a 2-dimensional array to store data, documented in this scala implementation: https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/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.

PDF link: http://www.eecs.harvard.edu/~michaelm/CS222/countmin.pdf