4 ms·

Is there a sound technique to get your k hash functions to produce k distinct bits, such that the original derivation would become correct?

TheRealPomax 6y ago
You had me until "such that the original derivation would become correct", which doesn't make a lot of sense?
- anonymoushn 6y ago
  Oh, you're right. The beginning of the original derivation assumes that the bits chosen by each hash function for a single input are independent (so it does not always produce k distinct bits) but the end assumes that it does produce k distinct bits. So it would still be incorrect. I expect that you would get a lower false-positive rate, though, if some inputs could not randomly query fewer than k bits of the filter!
  - gopiandcode 6y ago
    There are variants of the Bloomfilter that do try and do this - one way is to have each hash function map to a separate distinct subsequence of the bitvector. It does indeed reduce the false positive rate, but comes at the cost of increased space usage. As always, utility of this modification would depend on where you wanted to balance space-vs-accuracy constraints.
    - anonymoushn 6y ago
      I would hope not to use any additional space. A naive approach is to choose 1 bit out of N from the first hash, 1 out of the remaining N-1 from the second hash, and 1 out of the remaining N-2 from the third, and so on.
      - gopiandcode 6y ago
        That would fix the final independence problem, but it would also require further changes to other stages of the proof. For example, this strategy would then mean that when calculating the probability of a single bit being set, the hash outcomes are no longer independent, which means that a different expression would be needed. Additionally, from a practical sense, this variation might also be more costly to execute, as setting bits would go from a single memory access to a linear scan. I think it might be interesting to look into though.
        anonymoushn 6y ago
        You can decide which bits to set for an input in k^2 time I guess, not k*n time, then set each one with a single memory access.
    - xpe 6y ago
      It is two words: “Bloom filter”.
      - xpe 6y ago
        The original article used "Bloomfilter" instead of "Bloom filter". As of 2020-08-02, some of those mistakes have been corrected. Two mistakes remain.
marcan_42 6y ago
You could just keep hashing until you have enough non-colliding outputs, throwing away any collisions. This is sound as far as I can tell. Relatedly, mapping real hash functions to bits is also nontrivial to get 100% mathematically correct. As far as I know, the only sound way for hash functions with a fixed number of output bits and a non-power-of-two bloom filter is to truncate to the next power of two, then throw away any results that overflow the filter size and keep trying with new hashes (or repeated hashing). This is thus easy to integrate with avoiding duplicate bits, since you're retrying anyway. In practice, none of this matters, you can just take a hash output with enough extra bits modulo the Bloom filter size and call it a day. It'll be close enough to uniformly random and non-colliding anyway, for practical filters.
ReaLNero 6y ago
It's not too difficult: hash function 1 generates an integer from 0 to n-1, that index element is deleted, then hash function 2 generates an integer from 0 to n-2, that element is deleted etc. This is an O(n^2) algorithm, which you can improve to O(nlgn) using fenwick trees. In practice however, it is much quicker to generate random hashes and repeat until they're distinct.
- anonymoushn 6y ago
  In k^2 time, which is maybe faster than running a hash an additional time: function get_bits(input, hashes, n) local bits = {} for i=1,#hashes do local bit = hashes[i](input) % (n-i+1) for j=1,i-1 do if bits[j] <= bit then bit = bit + 1 end end bits[i] = bit while i > 1 and bits[i] < bits[i-1] do bits[i], bits[i-1] = bits[i-1], bits[i] i = i - 1 end end return bits end
  - marcan_42 6y ago
    Your % operation is not uniformly distributed if the hash domain isn't an integer multiple of the output size, which is a bigger problem for formal correctness than the colliding output issue (hashes are not uniformly distributed). You need to truncate to an even number of bits and retry until the output is < n, at which point you're retrying anyway, so you can just retry on collision instead of having all that complicated logic to skip bits. Nice try though, but if you want formally perfect results like the OP you have to try harder :-) (except real hash functions are only assumed to have perfectly distributed functions anyway, that is not proven and probably not provable, so basically you're screwed either way and none of this matters :-) ).
contravariant 6y ago
There's always the combinatorial number system. But it might be more effort than it's worth. As others have pointed out you can also just make the k^th hash pick any of the n-k remaining options.

TheRealPomax 6y ago

You had me until "such that the original derivation would become correct", which doesn't make a lot of sense?

anonymoushn 6y ago
Oh, you're right. The beginning of the original derivation assumes that the bits chosen by each hash function for a single input are independent (so it does not always produce k distinct bits) but the end assumes that it does produce k distinct bits. So it would still be incorrect. I expect that you would get a lower false-positive rate, though, if some inputs could not randomly query fewer than k bits of the filter!
- gopiandcode 6y ago
  There are variants of the Bloomfilter that do try and do this - one way is to have each hash function map to a separate distinct subsequence of the bitvector. It does indeed reduce the false positive rate, but comes at the cost of increased space usage. As always, utility of this modification would depend on where you wanted to balance space-vs-accuracy constraints.
  - anonymoushn 6y ago
    I would hope not to use any additional space. A naive approach is to choose 1 bit out of N from the first hash, 1 out of the remaining N-1 from the second hash, and 1 out of the remaining N-2 from the third, and so on.
    - gopiandcode 6y ago
      That would fix the final independence problem, but it would also require further changes to other stages of the proof. For example, this strategy would then mean that when calculating the probability of a single bit being set, the hash outcomes are no longer independent, which means that a different expression would be needed. Additionally, from a practical sense, this variation might also be more costly to execute, as setting bits would go from a single memory access to a linear scan. I think it might be interesting to look into though.
      - anonymoushn 6y ago
        You can decide which bits to set for an input in k^2 time I guess, not k*n time, then set each one with a single memory access.
  - xpe 6y ago
    It is two words: “Bloom filter”.
    - xpe 6y ago
      The original article used "Bloomfilter" instead of "Bloom filter". As of 2020-08-02, some of those mistakes have been corrected. Two mistakes remain.

marcan_42 6y ago

You could just keep hashing until you have enough non-colliding outputs, throwing away any collisions. This is sound as far as I can tell. Relatedly, mapping real hash functions to bits is also nontrivial to get 100% mathematically correct. As far as I know, the only sound way for hash functions with a fixed number of output bits and a non-power-of-two bloom filter is to truncate to the next power of two, then throw away any results that overflow the filter size and keep trying with new hashes (or repeated hashing). This is thus easy to integrate with avoiding duplicate bits, since you're retrying anyway. In practice, none of this matters, you can just take a hash output with enough extra bits modulo the Bloom filter size and call it a day. It'll be close enough to uniformly random and non-colliding anyway, for practical filters.

ReaLNero 6y ago

It's not too difficult: hash function 1 generates an integer from 0 to n-1, that index element is deleted, then hash function 2 generates an integer from 0 to n-2, that element is deleted etc. This is an O(n^2) algorithm, which you can improve to O(nlgn) using fenwick trees. In practice however, it is much quicker to generate random hashes and repeat until they're distinct.

anonymoushn 6y ago
In k^2 time, which is maybe faster than running a hash an additional time: function get_bits(input, hashes, n) local bits = {} for i=1,#hashes do local bit = hashes[i](input) % (n-i+1) for j=1,i-1 do if bits[j] <= bit then bit = bit + 1 end end bits[i] = bit while i > 1 and bits[i] < bits[i-1] do bits[i], bits[i-1] = bits[i-1], bits[i] i = i - 1 end end return bits end
- marcan_42 6y ago
  Your % operation is not uniformly distributed if the hash domain isn't an integer multiple of the output size, which is a bigger problem for formal correctness than the colliding output issue (hashes are not uniformly distributed). You need to truncate to an even number of bits and retry until the output is < n, at which point you're retrying anyway, so you can just retry on collision instead of having all that complicated logic to skip bits. Nice try though, but if you want formally perfect results like the OP you have to try harder :-) (except real hash functions are only assumed to have perfectly distributed functions anyway, that is not proven and probably not provable, so basically you're screwed either way and none of this matters :-) ).

contravariant 6y ago

There's always the combinatorial number system. But it might be more effort than it's worth. As others have pointed out you can also just make the k^th hash pick any of the n-k remaining options.