- cross-posted to:
- data_engineering
- cross-posted to:
- data_engineering
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.
I learned about Bloom filters from an article discussing how old systems and algorithms shouldn’t be forgotten because you never know when they’ll come in handy for another application. The example they gave was using Bloom filters to reduce data transmission for MMOs; break your world into sectors and just send everyone a Bloom filter of objects mapped to sectors, then the client can request more detail only for objects that are within a certain range of the individual PC.
That’s actually a really nice application, in this case to reduce bandwidth constraints as opposed to the usual use case of memory constraints!