What are Bloom filters?
medium.com
What are Bloom filters?
1–10 of 40 posts
Re: What are Bloom filters?
#2If 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.
Re: What are Bloom filters?
#3If 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?
Re: What are Bloom filters?
#4Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?
Re: What are Bloom filters?
#5Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?
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?
#6Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?
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?
#7Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?
Distributed Hash Table (DHT) networks often use them
Re: What are Bloom filters?
#8Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?
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.
Re: What are Bloom filters?
#9Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?
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?
#10Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?
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