magnuss / java-bloomfilter Goto Github PK

Your hash implementation has a problem. What you do is:

1. Generate a hash, for instance 128bit MD5 hash.
2. Split the hash in 4 byte chunks and interpret them a pseudorandom integers.
3. When a value is inserted in the bloomfilter: take each random int and do a modulo w.r.t. the size of the bloom filter

The last part is wrong/dangerous since it violates the assumption that hash values are evenly distributed over [1,m) with m being the size of the bloom filter. Here is why:
Suppose the bloom filter has a size of 3 billion. The hash value are integers so approximately uniformly distributed from 0 to roughly 4 billion. By taking the modulo the hash values between 0 and 1 billion get generated twice as often as the range 1 billion to 3 billion, as the range 3 billion to 4 billion is mapped to 0 - 1 billion. You should easily be able to verify that by taking a histogram of a large number of hashes.

This corruption of uniformity will lead to a decreased false positive rate and hence should be fixed (for instance by discarding the values which are two high instead of taking the modulo).

There was a change that said "Changed license from GPL to LGPL", but it just added the LGPL without removing the GPL. This makes the licensing a bit ambiguous. I'd love to give this a shot, but in a project which is LGPL, but not GPL, compatible.

Thanks,

83ec16e

I'm getting:
java.lang.ArithmeticException: / by zero
at com.skjegstad.utils.BloomFilter.contains(BloomFilter.java:345)

after creating filter with expectedNumberOfElements = 0 with constructor:
public BloomFilter(double falsePositiveProbability, int expectedNumberOfElements)
and check if it contains some element
What I'm expecting is either:

• false when calling contains
• exception on creation of filter which will tell me that 0 is bad value and I'm awful person that I passed it

i have import the bloomfiter in my program

but the program can errors a message

redis.clients.jedis.exceptions.JedisConnectionException: java.net.SocketException: Broken pipe (Write failed)
at redis.clients.jedis.Protocol.sendCommand(Protocol.java:104)
at redis.clients.jedis.Protocol.sendCommand(Protocol.java:84)
at redis.clients.jedis.Connection.sendCommand(Connection.java:127)
at redis.clients.jedis.BinaryClient.setbit(BinaryClient.java:912)
at redis.clients.jedis.Client.setbit(Client.java:671)
at redis.clients.jedis.Jedis.setbit(Jedis.java:2555)
at com.github.wxisme.bloomfilter.bitset.RedisBitSet.set(RedisBitSet.java:70)
at com.github.wxisme.bloomfilter.common.BloomFilter.add(BloomFilter.java:231)

so i can‘t find the problem

This library was used to develop and test Bloofi :

https://github.com/lemire/bloofi

(I am raising this issue merely to thank you for making the code available in the first place.)

Looks like the k should be a double.

public BloomFilter(int bitSetSize, int expectedNumberOElements) {
    this(bitSetSize / (double)expectedNumberOElements,
            expectedNumberOElements,
            (int) Math.round((bitSetSize / (double)expectedNumberOElements) * Math.log(2.0)));
}

It never hashes when the bitSetSize is 10, as an example.

For iterating through huge lists with duplicates and using the bloom filter to make sure each use of an item from the list is only done once, it might speed things up to have a combined containsAndAdd method to avoid hanging to hash the same input twice.

if (myBloom.contains(itemFromList)) {
  return;
}
myBloom.add(itemFromList);
//... do things ...

Hi,
Thanks you very much for your program. I wanted to use your program. I wanted to make the bloom filter size a fixed amount. how should I do that?

Thank you!

same as title