Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

let me butcher the concept for you :)

say though nummerology you reduce the character values of a name to a number 0-10. Lots of names will reduce to the same number. We take 11 bits and for "jim" we set the first bit. We have only one name in our data set so all other bits are 0. Now if someone types "joe" in the search box and it reduces to 2 we look at the second bit, see it is a zero and know 100% *for sure* that this name is not in the data set. If "jack" reduces to 1 and we look him up we see 1 is set so this name *might be* there.



Isn't this just similar to hash prefixes and not a true bloom filter?


I did say I'd butcher it. :-) imho one shouldn't be overly attached to an exact implementation but learn to reason about it. You could for example make an array and count how many times each bit was set. A textbook bloomfilter doesn't allow you to remove things but if you count how often a bit was set you obviously can.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: