Show HN: Bloom Filter • Hacker News Board

Re: Show HN: Bloom Filter

#11

Post by cjhanks » Tue, Jul 04, 2017, 10:13 PM UTC

joeblau wrote: post #9

This was the key to our data analytics url de-deuping platform back in 2011. We were pulling in 50k social media messages an hour and there were lots of duplicate links running though our pipeline. We had a 100GB bloom filter backed by Redis to keep a list of all links that came though our system and it worked beautifully.

A 100GB bloom filter? What does that mean? How many hash functions.. how many bits?

Re: Show HN: Bloom Filter

#12

Post by bane » Tue, Jul 04, 2017, 11:34 PM UTC

cjhanks wrote: post #11

joeblau wrote: post #9

This was the key to our data analytics url de-deuping platform back in 2011. We were pulling in 50k social media messages an hour and there were lots of duplicate links running though our pipeline. We had a 100GB bloom filter backed by Redis to keep a list of all links that came though our system and it worked beautifully.

A 100GB bloom filter? What does that mean? How many hash functions.. how many bits?

I would guess that a 100GB bloom filter would have 800 gigabits.

You can make some guesses, with 7 hashes and a false probability of 1%, a bloom filter designed on a cardinality of 100 billion elements is a little over 100GB.

Re: Show HN: Bloom Filter

#13

Post by bane » Tue, Jul 04, 2017, 11:39 PM UTC

You can get lots of mileage out of bloom filters as well by just using them off of disk. If you're smart about it and use mmap'd files, you only ever end up reading a few bytes at a time. On modern SSDs you can get some really incredible performance not too far off using them in RAM, or you can use a bunch of them for a simple classifier.

here's an implementation: https://axiak.github.io/pybloomfiltermmap/