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

Interactive Demo of Bloom Filters

jasondavies.com

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Interactive Demo of Bloom Filters

#41

Post by afonsotsukamoto »

tekromancr wrote: post #16
cr0sh wrote: post #13

Am I understanding this correctly? 1) For each key, you generate a "hash" - which is a bit position 2) The hash generation is such to ensure that the bit location in the filter is probabilistically distributed for each key (so they are spread "evenly", for lack of a better term, over the length of the filter) 3) You generate so many locations per key, the number of which is the number of hash generators you are using…

Pretty close. Except 1) you generate multiple hashes for a particular value, thus setting multiple bits for a value 5) when this happens, you use a larger filter 6) You can also determine with 100% confidence that a value isn't in the set. Other than that, I think you have a good idea of what it's about. Once I learned about this, I got tons of great ideas. Right now, I think it would be cool to construct a bloom fil…

I do believe on the 100% confidence, but when you have full filter is that still meaningful? As in - are there still any gains on using a bloom filter in this case?

I know that is sort of a corner case, but in that situation the 100% confidence case happens 0% of the times which makes the filter a bit useless - no?

Just trying to understand what are the limitations as been super curious about bloom filters for a long time

Re: Interactive Demo of Bloom Filters

#42

Post by tekromancr »

afonsotsukamoto wrote: post #41
tekromancr wrote: post #16

Earlier quoted context omitted.

Pretty close. Except 1) you generate multiple hashes for a particular value, thus setting multiple bits for a value 5) when this happens, you use a larger filter 6) You can also determine with 100% confidence that a value isn't in the set. Other than that, I think you have a good idea of what it's about. Once I learned about this, I got tons of great ideas. Right now, I think it would be cool to construct a bloom fil…

I do believe on the 100% confidence, but when you have full filter is that still meaningful? As in - are there still any gains on using a bloom filter in this case? I know that is sort of a corner case, but in that situation the 100% confidence case happens 0% of the times which makes the filter a bit useless - no? Just trying to understand what are the limitations as been super curious about bloom filters for a long…

You are correct.

The filter is completely useless if it is filled with 1s. In this situation, you would just use a larger filter. I am not sure exactly what the ideal size is, it depends on the desired probability of false positives, but an optimally large filter for the data you are using will have some empty bits.

Re: Interactive Demo of Bloom Filters

#43

Post by in9 »

SatvikBeri wrote: post #33
in9 wrote: post #32

What is the efficiency of this algorithm? Is this how one can check for used usernames when a user is creating an account?

Wouldn't a database lookup (with an index) be fast enough in that case? IIRC that's what Reddit does.

I have read about what reddit does, but idk if it was a simple (or hashed) database lookup or maybe a BF.

Re: Interactive Demo of Bloom Filters

#44

Post by bane »

ThePhysicist wrote: post #2

If you're interested in using Bloom filters in the backend, we (at DCSO) have written efficient and interoperable open-source implementations in Python and Go, also using FNV-1 hashing: https://github.com/DCSO/bloom (Go version) https://github.com/DCSO/flor (Python version) The Go version comes with a command line tool that allows you to use Bloom filters on the shell.

One note: if you've done everything correctly under the hood, instead of reading and writing the entire filter into and out of memory, just mmap the file and operate on it directly. It turns out to be pretty fast, especially on SSDs and you can make both many filters and test them quickly this way, or make filters that are practically larger than RAM and swap partitions and make absolutely enormous sets.

Re: Interactive Demo of Bloom Filters

#45

Post by bane »

tekromancr wrote: post #42
afonsotsukamoto wrote: post #41

Earlier quoted context omitted.

I do believe on the 100% confidence, but when you have full filter is that still meaningful? As in - are there still any gains on using a bloom filter in this case? I know that is sort of a corner case, but in that situation the 100% confidence case happens 0% of the times which makes the filter a bit useless - no? Just trying to understand what are the limitations as been super curious about bloom filters for a long…

You are correct. The filter is completely useless if it is filled with 1s. In this situation, you would just use a larger filter. I am not sure exactly what the ideal size is, it depends on the desired probability of false positives, but an optimally large filter for the data you are using will have some empty bits.

Here's a helpful calculator, it will even tell you the optimal number of hash functions. All you have to know is the expected cardinality of the set.

https://hur.st/bloomfilter

Re: Interactive Demo of Bloom Filters

#46

Post by taeric »

avaer wrote: post #19

I think CS education would be improved if these concepts didn't have mysterious names. Respect to Bloom, but the programming median might be raised if Bloom filters were called something stupid obvious like Hash Array Filler-upper Tables. We might not even need to spend time making visualizations to explain them.

Last time this came up, I gave my wish that these had been called something like a Concierge filter. The metaphor being that you can ask the concierge of a hotel several questions about people that have been seen entering to get an idea if a given person is probably there.

Re: Interactive Demo of Bloom Filters

#47

Post by taeric »

greenpizza13 wrote: post #34
SatvikBeri wrote: post #33

Earlier quoted context omitted.

Wouldn't a database lookup (with an index) be fast enough in that case? IIRC that's what Reddit does.

Presumably you have indexed based on username or the hash of a username, so the lookup is very inexpensive.

You could also send the bloom filter down to the client to filter out client side with high probability.

Re: Interactive Demo of Bloom Filters

#48

Post by avmich »

netcraft wrote: post #4

obligatory mention that if you are interested in this you should also know about cuckoo filters: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://en.wikipedia.org/wiki/Cuckoo_hashing

I also found this - https://bdupras.github.io/filter-tutorial/ - interesting.

Re: Interactive Demo of Bloom Filters

#49

Post by joeblau »

in9 wrote: post #32

What is the efficiency of this algorithm? Is this how one can check for used usernames when a user is creating an account?

They are also helpful in terms of space savings. I worked at a startup in Palo Alto in 2011 where we used a 100 GB in memory (Redis) Bloom Filter to de-duplcate links coming in from a real-time social media stream (Facebook, Twitter, Forums, etc..). While Bloom Filter does introduce false positives (collisions) we were willing to take the bet on that rather than allowing duplicate social media posts in our pipeline.

If we wanted to store this information in a regular hash table, we would require a lot more space than the 1 bit per entry of a Bloom Filter.

Re: Interactive Demo of Bloom Filters

#50

Post by afonsotsukamoto »

bane wrote: post #45
tekromancr wrote: post #42

Earlier quoted context omitted.

You are correct. The filter is completely useless if it is filled with 1s. In this situation, you would just use a larger filter. I am not sure exactly what the ideal size is, it depends on the desired probability of false positives, but an optimally large filter for the data you are using will have some empty bits.

Here's a helpful calculator, it will even tell you the optimal number of hash functions. All you have to know is the expected cardinality of the set. https://hur.st/bloomfilter

ah! ok - I just had a "mind bending" moment after looking at the calculator + tekromancr's response.

I thought we would want to control the number of hash functions (k) and the number of items (n) but I guess the most common use case will be to set the allowed probability of a false positive for the number of allowed items and let the "system" control the k and m (hash functions and bits in the filter)

Enlightening!

One question remains though - since the number of bits (m) is a function of the probability of false positives (p) and the number of hash functions (k) is a function of the number of bits and the number of items (n), does it mean that once we start a bloom filter we can't update the number of items or the desired probability of false positives?

My assumption is that if we change p, then m will change, which would make the k functions "obsolete" as they're being "mapped" to a new sized m. Same for n, which would change the k functions, making it so that a new item would be hashed differently, making m hits/misses obsolete again.

Might be missing something here though.

Either way, I still find bloom filters a fascinating data structure.

Post reply on HN