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

51–56 of 56 posts

Re: Interactive Demo of Bloom Filters

#51

Post by geocar »

taco_emoji wrote: post #25
geocar wrote: post #5

If anyone just wanted to see a collision: a 2 c collides with: f

Another anomaly is that "hello" yields the same array position for all three hashes, which makes it highly prone to collision.

Same with:

    The Answer to The Ultimate Question of Life, The Universe, and Everything.
which means that if

    FORTY-TWO.
has been inserted, you'll find that as a possible answer.

Re: Interactive Demo of Bloom Filters

#52

Post by [deleted] »

jolmg wrote: post #30
avaer wrote: post #27

Earlier quoted context omitted.

You know what both a Hash and Array are, as would ~100% of the people who care about Bloom filters.

His point still stands, though. :) Those who already know what a Bloom Filter is would probably the find the name more convenient than having to say a short description every time. Those that are just learning programming might argue that Hash, Array, Boolean, String, etc. would be understood faster if they had more descriptive names. Having a short, distinctive name helps in differentiating and reasoning about the d…

[deleted]

Re: Interactive Demo of Bloom Filters

#53

Post by SyneRyder »

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.

While I'm not sure I agree about mysterious names, I do get confused whenever Bloom filters are mentioned on HN. I always think they're about bloom filters as applied to computer graphics:

https://en.wikipedia.org/wiki/Bloom_(shader_effect)

Re: Interactive Demo of Bloom Filters

#54

Post by tekromancr »

afonsotsukamoto wrote: post #50
bane wrote: post #45

Earlier quoted context omitted.

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!…

Nope, I think you got it. My understanding is that if you want to change the params, you need to rebuild the filter.

Re: Interactive Demo of Bloom Filters

#55

Post by natch »

chrisseaton wrote: post #9
natch wrote: post #3

You don't need more than one hash function. Just append an incrementing token onto the input before each successive hash.

> Just append an incrementing token onto the input before each successive hash. But that's a new hash function then.

Obviously not. It's a new input into the same hash function.

Re: Interactive Demo of Bloom Filters

#56

Post by ThePhysicist »

bane wrote: post #44
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.

Yes good point, we actually have this on the roadmap!
Post reply on HN