Bloom Filters by Example

Definitely not clear from the article alone. You can use more than one hash algorithm to reduce the chance of collisions. You set the values in the bit array for both hashes, and then you check both again.

Practical, contrived example: the string "w" gives us "2" from fnv and "11" from murmur. When you add that to the filter with both hashes, bits 2 and 11 are set.

The string "h" gives us 2 from fnv and 10 from murmur. If you were using only the fnv hash, you'd get a "maybe exists" result. But since the murmur hash is different for "h" than it is for "w", you get a "definitely not" result.

Of course, you still have collisions, you just cut them down. Both fnv and murmur return the same hashes for "w" and "woot", so adding "w" then checking "woot" still gives you a "maybe" result, but at least checking "h" does not.

Re: Bloom Filters by Example

#5

Post by natch » Mon, Jul 10, 2017, 11:35 PM UTC

I disagree with the standard dogma around bloom filters that you need multiple hash functions. Just use a simple incrementing salt value to modify the input so you can hash the resulting salted input as many times as you need to, using a different salt value each time.

Say you want to hash the string "abc" 8 times. Instead of having 8 hash functions, just take the hash of, say, "abc-0", "abc-1", ... "abc-7". As long as your hash function is of good quality and you're treating the output properly, you don't have to worry about the results from these different inputs having some significant relationship. For cryptographic types maybe I'm using the term "salt" loosely. Whatever, think of another term if you like. Anyway in practice this has worked fine for me.

Re: Bloom Filters by Example

#6

Post by btilly » Mon, Jul 10, 2017, 11:56 PM UTC

natch wrote: post #5

I disagree with the standard dogma around bloom filters that you need multiple hash functions. Just use a simple incrementing salt value to modify the input so you can hash the resulting salted input as many times as you need to, using a different salt value each time. Say you want to hash the string "abc" 8 times. Instead of having 8 hash functions, just take the hash of, say, "abc-0", "abc-1", ... "abc-7". As long…

That's just an easy way to create new hash functions out of an existing one. Nobody sensible would insist that your hashes must have different underlying algorithms, just that they produce uncorrelated outputs.

Re: Bloom Filters by Example

#7

Post by FreakLegion » Tue, Jul 11, 2017, 12:11 AM UTC

natch wrote: post #5

I disagree with the standard dogma around bloom filters that you need multiple hash functions. Just use a simple incrementing salt value to modify the input so you can hash the resulting salted input as many times as you need to, using a different salt value each time. Say you want to hash the string "abc" 8 times. Instead of having 8 hash functions, just take the hash of, say, "abc-0", "abc-1", ... "abc-7". As long…

See "Less Hashing, Same Performance: Building a Better Bloom Filter": https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.p.... This is pretty standard practice now.

There've been a couple of other analyses (at least) of the importance of independence among hash functions in probabilistic data structures --- which if I remember correctly was "not as much as you'd think" --- but I don't remember the titles of the papers offhand.

Re: Bloom Filters by Example

#8

Post by natch » Tue, Jul 11, 2017, 12:42 AM UTC

btilly wrote: post #6

natch wrote: post #5

I disagree with the standard dogma around bloom filters that you need multiple hash functions. Just use a simple incrementing salt value to modify the input so you can hash the resulting salted input as many times as you need to, using a different salt value each time. Say you want to hash the string "abc" 8 times. Instead of having 8 hash functions, just take the hash of, say, "abc-0", "abc-1", ... "abc-7". As long…

That's just an easy way to create new hash functions out of an existing one. Nobody sensible would insist that your hashes must have different underlying algorithms, just that they produce uncorrelated outputs.

You haven't been reading the blog posts on bloom filters. Or maybe you're saying they're not sensible, in which case I agree.

Re: Bloom Filters by Example

#9

Post by Freaky » Tue, Jul 11, 2017, 12:57 AM UTC

That seems a roundabout way of sizing a bloom filter. Here's what I came up with when I first implemented them for Newzbin: https://hur.st/bloomfilter

    m = ceil((n * log(p)) / log(1.0 / (pow(2.0, log(2.0)))));
    k = round(log(2.0) * m / n);

Re: Bloom Filters by Example

#10

Post by natch » Tue, Jul 11, 2017, 1:02 AM UTC

FreakLegion wrote: post #7

natch wrote: post #5

I disagree with the standard dogma around bloom filters that you need multiple hash functions. Just use a simple incrementing salt value to modify the input so you can hash the resulting salted input as many times as you need to, using a different salt value each time. Say you want to hash the string "abc" 8 times. Instead of having 8 hash functions, just take the hash of, say, "abc-0", "abc-1", ... "abc-7". As long…

See "Less Hashing, Same Performance: Building a Better Bloom Filter": https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.p... . This is pretty standard practice now. There've been a couple of other analyses (at least) of the importance of independence among hash functions in probabilistic data structures --- which if I remember correctly was "not as much as you'd think" --- but I don't remember the titles of…

Standard practice? Someone should tell all the fresh CS grads who keep blogging about their multiple hash algorithms. I've been doing this as standard practice since the 1990s. I'm glad if Computer Science academics are catching up to the working practitioner.