11–20 of 39 posts
If testing for membership in the set is unreliable, but testing for non-membership in the set works every time, then why can't you simply invert the boolean for the non-membership test and call that a membership test?
E.g., if it's not not in the group, then it's in the group...
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…
PRs welcome, I'm on vacation and unlikely to get to it immediately. http://github.com/llimllib/bloomfilter-tutorial
Unrelated, but I've always had this question about bloom filters... If testing for membership in the set is unreliable, but testing for non-membership in the set works every time, then why can't you simply invert the boolean for the non-membership test and call that a membership test? E.g., if it's not not in the group, then it's in the group...
For example, consider a Bloom filter checking the availability of a username during sign up. If you want an inverse Bloom filter that checks if it is not not in the group, then you need to load it with all possible usernames.
Unrelated, but I've always had this question about bloom filters... If testing for membership in the set is unreliable, but testing for non-membership in the set works every time, then why can't you simply invert the boolean for the non-membership test and call that a membership test? E.g., if it's not not in the group, then it's in the group...
If you want to invert the boolean check, then you need to invert the input space as well, which is not possible. For example, consider a Bloom filter checking the availability of a username during sign up. If you want an inverse Bloom filter that checks if it is not not in the group, then you need to load it with all possible usernames.
Earlier quoted context omitted.
If you want to invert the boolean check, then you need to invert the input space as well, which is not possible. For example, consider a Bloom filter checking the availability of a username during sign up. If you want an inverse Bloom filter that checks if it is not not in the group, then you need to load it with all possible usernames.
Makes sense. OP's link is interactive enough that I was beginning to see that, though couldn't articulate it. Thanks!
In computing terms the interface has 2 methods:
- takeALookAtThisFace(x)
- yaSeenThisFaceBefore?(x) which returns either "no way" or "hmm, I guess so".
"no way" means P(x is a member) = 0. Its negation is not "hell yes" (P(x is a member) = 1), it's "maybe" (P(x is a member) > 0).
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…
Earlier quoted context omitted.
Makes sense. OP's link is interactive enough that I was beginning to see that, though couldn't articulate it. Thanks!
If I was going to explain a bloom filter like you're 5... a bloom filter is like a savant who never forgets a face -- maybe he's got a job in passport control in Arstotzka -- if you show him someone's face or picture once, he'll never forget it: if any time later you show him the same picture and ask him "have you seen this face before?" he'll say "yes" without fail. If he replies "no way", you can be 100% sure he's…
> cryptographic hashes such as sha1,
> though widely used therefore are not
> very good choices
> [the more times you hash it the fewer
> false positives]
For instance, suppose you were implementing a Bloom filter with 2^20 bits, and you want to use 10 bits per item. Instead of hashing the item 10 times, could you hash once with a 256 bit cryptographic hash, and then take the lower 200 bits, divide that into 10 bit strings of 20 bits each, and use those?