Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What are Bloom filters?

medium.com

Post reply on HN
Print view View original

11–20 of 40 posts

Re: What are Bloom filters?

#11

Post by bcheung »

bbcbasic wrote: post #4

Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?

They are typically used when you have a lot of items in a list of some kind and you want to know if a particular one is present already without incurring the heavy lookup cost.

When you check the Bloom filter it tells you:

1) it might be there

or

2) it definitely isn't there.

In the case of 2, you don't need to look it up. In case 1, you'll need to do the actual lookup.

It is commonly used to filter high volume / frequency requests for something. For example, if you have a list of banned IP addresses, user accounts, etc, you can quickly go through the bloom filter without hitting the database.

Re: What are Bloom filters?

#13

Post by jasode »

>To understand Bloom filters, you first have to understand hashing.

As pedagogy, I think this is the wrong approach.

The author already knows Bloom filters and therefore, it seems like the most logical thing to first talk about is hash functions because that's how it's implemented.

Unfortunately, that's not how a person brand new to the concept thinks about it. The first thing to talk about is motivations and scenarios and use cases.

For that, the first 2 paragraphs of wikipedia article[1] on Bloom filters is fairly straightforward. It explains why it's an interesting technique. Imo, those paragraphs are a better introduction than the author's dive right into "hash functions" immediately after unrelated blurbs of "I put my fork down" and "my wife shakes her head with a rueful smile."

[1]https://en.wikipedia.org/wiki/Bloom_filter

Re: What are Bloom filters?

#16

Post by parshimers »

bbcbasic wrote: post #4

Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?

They are very useful in log structured merge tree (LSM) based storage. HBase uses them, for example. The idea is to have a bloom filter as part of each on-disk component, so that one can look at the bloom filter first- and then only bother with searching the actual component, if there is a match in the filter. That way you can reduce the pain of having to potentially search multiple indices on disk.

Re: What are Bloom filters?

#17

Post by Freaky »

mortehu wrote: post #8
SCHiM wrote: post #6

Earlier quoted context omitted.

I've programmed bloomfilters for my job. A certain product of ours keeps track of certain urls visited. We're talking millions of (unique) urls. We use bloomfilters to quickly check if a url was visited or not. If the bloomfilter search is positive a more expensive search inside a log file begins that gives a conclusive result (since bloomfilters have a (very) small false positive-rate, but we want to be perfectly su…

> bloomfilters have a (very) small false positive-rate One of the neat things about Bloom filters is that you can choose your own false positive rate, by tuning the number of hashes and the storage size.

Calculator: http://hur.st/bloomfilter

Re: What are Bloom filters?

#18

Post by notacoward »

jamra wrote: post #3
notacoward wrote: post #2

If Bloom filters look interesting, you should probably also check out cuckoo filters. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf The differences are somewhat subtle, but the use cases overlap a lot.

Would it be safe to say that Cuckoo filters are bloom filters with some additional overhead for the ability to add and remove?

Deletion is the big difference, but even without that I think there can be other significant differences as well. For any given number of items, it can be pretty unclear which one will give better performance (including the cost of false positives) for bounded size, or better space efficiency for bounded performance. Usually you'll need at least an accurate model for both, if not an actual implementation.

Re: What are Bloom filters?

#20

Post by Freaky »

bbcbasic wrote: post #4

Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?

At Newzbin we used them for reducing load on MySQL during Usenet header fetching - each new header would have the Message-ID put through a filtering service to check if it had already been inserted.

The service kept an array of 7 filters, rotated daily - the oldest would be cleared and reused for new items, giving us 6-7 days of history. Each individual header was low-value, and a few false positives every week wasn't a big deal - Usenet servers lost a lot more during their normal course of operation.

Post reply on HN