Data Engineering

440 readers

1 users here now

A community for discussion about data engineering

Icon base by Delapouite under CC BY 3.0 with modifications to add a gradient

founded 2 years ago

MODERATORS

ericjmorey@programming.dev

Bloom filters: real-world applications (llimllib.github.io)

submitted 2 years ago by Reader9@programming.dev to c/data_engineering@programming.dev

4 comments fedilink hide all child comments

cross-posted from: https://programming.dev/post/2656516

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

[–] drdabbles@lemmy.world 4 points 2 years ago (3 children)

A bloom filter tells you that an element is not in a set, or maybe is in a set. The only guaranteed accurate result is not in set. You also have to reproduce the filter whenever you remove items from the set being tested, which isn't a free operation.

I've seen bloom filters abused in a lot of ways that make no sense, but very few ways that do. The classical example of scanning a k:v space in a memory efficient manner is the best application I've seen, but it still doesn't really work if you need to know a key is definitely in that space. You still have to perform the lookup.

An application for bloom filter I was working on was mitigating the effects of abusive lookups for non-existent names on a DNS platform, and it turned out that even with absurdly high lookup rates, adding an initial check for negative presence in a record set, we didn't benefit at all.

[–] Reader9@programming.dev 2 points 2 years ago

I can see why this data structure might be abused and/or chosen for an inappropriate use-case since it seems to offer a lot of value for the tiny amount of space required.

if you need to know a key is definitely in that space. You still have to perform the lookup.

This is a good description. I think the name “filter” is appropriate for their best use cases, when you want to remove members of some other set if they are probably members of the bloom filter set, and can accept that you might remove some extras due to false positives.

Problems like that come up from time-to-time.

load more comments (2 replies)