BloomFilter doesn't work when amount of bits > 2^32

[ajtkulov]

In my live case, we need BloomFilter for a bigger amount (about 4-5Gb ram, >32B bits)

The code is dependent on java.util.BitSet with .ctor

public BitSet(int nbits) with a lot of getter/setter by int index.

[abramsm]

Can you partition your data in some way so that you can than use a list of n smaller BloomFilters to hold each chunk of data?

[ajtkulov]

it would work, but as a drawback, you have to query each chunk for contains method. So, complexity increases by N (chunk amount). Add method also becomes more sophisticated.

Actually, I have a "solution" (I'm not a java native, so excuse me in advance). There is a fork, there is a lot of copy-paste code: own BitSet with long type and BloomFilter hierarchy. https://github.com/ajtkulov/stream-lib It works, but I'm not sure that this is idiomatic for java and enough for PR.

[vitusya]

why complexity increase by N chunks? you need partition your data by hash, index_of_bloom = long_hash % number_of_chunks, complexity is same, memory complexity is num_chunks * bloomfilter_memory

[ajtkulov]

@vitusya agree, thank you, it's much much easier.

The only theoretical issue is that (in case you build Bloom from dynamic data) some malicious person could generate items related to the same bucket. But it's related to all hashes structures, and it's a theory, not a practical thing.