News for hackers. Stuff that matters.
Re:What are Bloom filters? by bbcbasic on Monday July 20, 2015 @04:49PM (#9918964)
Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?
Re:What are Bloom filters? by gopalv on Monday July 20, 2015 @04:58PM (#9919037)
All the time - [1]/[2]

When you are going to fetch data from a remote location, you don't want to make a trip in vain.

So you end up storing them as a fixed size metadata chunk that lets you guess whether to go fetch it or not.

The neat trick is that the bloom filters have no false-negatives - the data might not exist (false positives), but it will never say "no" if it does exist.

But unfortunately, it doesn't really support deletion neatly - so it's really useful for scenarios where it's a first point of lookup before overloading a central source-of-truth.

The best use case I've seen for it is in Chrome, where the "Safe browsing" list is actually a huge bloom filter, which is used to decide whether to ask Google if this domain is safe.

So the list of banned URLs might be in the millions, but the bloom filter is a few megabytes and when it has a false positive, it goes & checks upstream whether it is indeed still banned/problematic.

[1] - http://www.slideshare.net/Hadoop_Summit/orc-2015-faster-bett... [2] - https://issues.apache.org/jira/browse/HIVE-11306

Re:What are Bloom filters? by mbrubeck on Monday July 20, 2015 @04:52PM (#9918984)
Web browsers use bloom filters for filtering out CSS rules during selector matching. Here's the implementation of this in Servo (the project I work on): https://github.com/servo/servo/pull/3212

I believe browsers also store their Safe Browsing (anti-malware/phishing) blacklists in bloom filters.

Re:What are Bloom filters? by pronoiac on Monday July 20, 2015 @06:19PM (#9919485)
I've used them before. I ran a Squid proxy and connected it to the NLANR cache hierarchy[1]; despite the name, it's more of a mesh with siblings. For the best speed, you can use bloom filters (or cache digests, in their terms[2]) to avoid the extra latency of a request of "hey, do you have this URL cached?" from someone who definitely doesn't.

[1] http://wiki.squid-cache.org/Features/CacheHierarchy

[2] http://wiki.squid-cache.org/SquidFaq/CacheDigests

Re:What are Bloom filters? by colordrops on Monday July 20, 2015 @05:16PM (#9919151)
They are used in Cassandra to determine whether or not to make a request to another node for data.
Re:What are Bloom filters? by bcheung on Monday July 20, 2015 @05:01PM (#9919049)
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? by miketuritzin on Monday July 20, 2015 @04:57PM (#9919024)
The first time I heard of bloom filters was back when I worked at Google a decade ago (on the search indexing team). We used them in MapReduces when doing cross-machine table lookups. The idea was to load the bloom filters into memory on the machines doing the lookups and then to only do the lookup if the bloom filter test passed - this optimization worked because a large fraction of the lookups were for entries not contained in the tables.

I can't actually remember what data was being looked up in the tables, though.

Re:What are Bloom filters? by Freaky on Monday July 20, 2015 @05:34PM (#9919263)
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.

Re:What are Bloom filters? by SCHiM on Monday July 20, 2015 @04:54PM (#9918999)
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 sure).

Re:What are Bloom filters? by mortehu on Monday July 20, 2015 @04:57PM (#9919023)
> 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.

Re:What are Bloom filters? by Freaky on Monday July 20, 2015 @05:20PM (#9919166)
Re:What are Bloom filters? by parshimers on Monday July 20, 2015 @05:17PM (#9919155)
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? by bobthecowboy on Monday July 20, 2015 @05:10PM (#9919110)
Ceph (the distributed storage platform) uses them for their cache tier to determine if a piece of data is "hot" enough to cache.
Re:What are Bloom filters? by simi_ on Monday July 20, 2015 @07:14PM (#9919708)
Yes! We use them to check for weak passwords server-side. (Passwords arrive already hashed, we have a large dataset of known bad passwords that we load when the application starts.)

https://github.com/lavab/api/search?utf8=%E2%9C%93&q=bf

Re:What are Bloom filters? by gdubya on Monday July 20, 2015 @04:56PM (#9919020)
Distributed Hash Table (DHT) networks often use them
Re:What are Bloom filters? by joeldg on Monday July 20, 2015 @06:03PM (#9919419)
spellcheckers use them, any time you see a company with millions of users let you know your email address was already registered, domain name registrars use them -- basically anything with a large search space where you need to know if something is in (or not) the dataset. They are useful all over. I wrote a modified version of bloom filters so the filter files are about 1/3rd the size (but with a slight cpu tradeoff) for a domain name registrar. They are kind of a staple of computer science.