Comment by RiderOfGiraffes | Hacker News Reader

Comment by RiderOfGiraffes | Hacker News Reader

RiderOfGiraffes

Not sure what your confusion is, but here's an explanation ...

A Bloom Filter lets you know, for each object I feed you, whether you've seen it before or not.

You could just take a copy of each one and compare the one I feed you against all the ones you have, but that has some disadvantages. (I'll leave it as an exercise to name some of them)

An alternative is to take a hash of each object I feed you and then keep the hash. Then when I give you an item you hash it and see if you have the hash. There's always a chance that you'll say "yes" because of a coincidence, but you'll never say "No" when you shouldn't. That also has disadvantages. In particular, for example, you don't know how big your storage space will have to get, and lookup times can get very inconvenient.

So here's how a bloom filter works. Take a very long vector of 0/1, and set them all to 0. Also choose 10 (for some value of 10) hash functions that map an object to an apparently random place in the vector. When you get given an object, set all those semi-random places to a 1.

Now when I give you an object, you check to see that all the places are set to 1. If not, then the object I've given you can't be one you've seen. On the other hand, if they are all set to 1, then very likely that's because you've seen this object before. It's not certain, but you can make the probability of error really, really small.

With any luck that will let you read and understand the wikipedia entry.

http://en.wikipedia.org/wiki/Bloom_filter

Thanks. My only remaining point of confusion is what the 10 hash functions are doing? Does each one set one bit in your vector? Does that mean you need a hash function that takes a string as input and returns 0 or 1?

Each hash function indicates a bit to set. If you have an array of 2^n bits, then the hash function must return an n-bit number.

No, each hash function tells you a bit to set. Your hash functions each take an input object and return a location in the vector. That location is set to 1.

With regards how big to make things, you need to do the math. If you have a vector of 1000 bits in your vector and you have 10 hash functions then there are 1000^10 = 10^30 possible collections of ten bits that can be set. If your plausible collection is only of size a few billion then coincidences won't be common or frequent.

256 bytes is 2048 bits, 16 hash functions, suddenly there are 2048^16 possible combinations, or 2^176 which is about 10^50.

So why is this an improvement over an ordinary hash table? Does having more than one hash function help in some way?

Er, I've just shown that you can store several billion records in a bit vector of length 256 bytes and you ask why it's better than a hash table? There's something that at least one of us isn't understanding ...

Thanks for taking the time to explain this along with the 1000bits and 256bits example. I've known about bloom filters for quite some time, but never quite understood the statistics.

In my area of research, sequence alignments (aka. sequence comparisons), pruning the search space is immensely important; the absence of false negatives is a huge win.

Also how do you decide how long to make the vector?

It's a tradeoff between space and probability that your bloom filter will return "yes" when it actually hasn't seen the item (and technically number of times you want to perform a hash function for each lookup).

There are a number of calculators and tables that let you pick the ratio of bits to number of items and the number of hashes and spit out a probability, eg:

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.htm...

Reply on news.ycombinator.com