3 ms·

For those of you who don't know what a Bloom Filter is or the concept isn't quite clear, you should check out this site: http://www.jasondavies.com/bloomfilter/

by jonpaul 14y ago

For those of you who don't know what a Bloom Filter is or the concept isn't quite clear, you should check out this site: http://www.jasondavies.com/bloomfilter/ http://www.jasondavies.com/bloomfilter/ He has a nice interactive demo with an explanation on how it works.

llimllib 14y ago
The demo I wrote falls somewhere in between these two: http://billmill.org/bloomfilter-tutorial/ http://billmill.org/bloomfilter-tutorial/ I like Jason's demo and graphic better, but I go into a bit more detail. The blog post under discussion goes into much more detail than me, and assumes a bit more knowledge of the reader.
peacemaker 14y ago
Unless I'm misunderstanding how a Bloom Filter works, I don't think the interactive demo is working correctly. If you add letters a - z as keys, then do a search for some numbers, such as the number 6, you get "Probably there". I was under the impression that a Bloom Filter could determine if something was definitely NOT in the data set, in which case this the example isn't working. Please correct me if I'm wrong :) EDIT: After playing around with it some more I'm questioning if I do fully understand how it is supposed to work. It seems there are many cases of "Probably there" when the key definitely is not. So I'm guessing in those cases you'd want to search the set to make sure?
- mej10 14y ago
  You are slightly confused. False positives do indeed happen, but false negatives can never happen (if one of the bits aren't set for the corresponding hash, then it is guaranteed to have never been added before). Collisions in hash tables are related to false positives in Bloom Filters. Also, regarding your last statement: You don't always need to look at the actual set in some cases, but for a lot you do. Bloom Filters give you a fast, compact way to prevent a lot of unnecessary searching. Spell Checkers, for example, you could reduce the amount of times you had to search through the dictionary, or for finding files or something on disk, you could eliminate a percentage of searches for the files. How much these can be reduced is related to the size of your Bloom filter.
  - peacemaker 14y ago
    Ok that makes sense, thanks for taking the time to explain. Seems obvious now! :)

by jonpaul 14y ago

llimllib 14y ago

The demo I wrote falls somewhere in between these two: http://billmill.org/bloomfilter-tutorial/ http://billmill.org/bloomfilter-tutorial/ I like Jason's demo and graphic better, but I go into a bit more detail. The blog post under discussion goes into much more detail than me, and assumes a bit more knowledge of the reader.

peacemaker 14y ago

Unless I'm misunderstanding how a Bloom Filter works, I don't think the interactive demo is working correctly. If you add letters a - z as keys, then do a search for some numbers, such as the number 6, you get "Probably there". I was under the impression that a Bloom Filter could determine if something was definitely NOT in the data set, in which case this the example isn't working. Please correct me if I'm wrong :) EDIT: After playing around with it some more I'm questioning if I do fully understand how it is supposed to work. It seems there are many cases of "Probably there" when the key definitely is not. So I'm guessing in those cases you'd want to search the set to make sure?

mej10 14y ago
You are slightly confused. False positives do indeed happen, but false negatives can never happen (if one of the bits aren't set for the corresponding hash, then it is guaranteed to have never been added before). Collisions in hash tables are related to false positives in Bloom Filters. Also, regarding your last statement: You don't always need to look at the actual set in some cases, but for a lot you do. Bloom Filters give you a fast, compact way to prevent a lot of unnecessary searching. Spell Checkers, for example, you could reduce the amount of times you had to search through the dictionary, or for finding files or something on disk, you could eliminate a percentage of searches for the files. How much these can be reduced is related to the size of your Bloom filter.
- peacemaker 14y ago
  Ok that makes sense, thanks for taking the time to explain. Seems obvious now! :)