[XLattice-devel] XLATTICE - bloom filters

[Emi <em...@gm...>]

Hi,
I am looking into the crypto package and am trying to understand a couple of
things about the bloom filter implementation. I am a little bit confused on
why there is the restriction on the size of the bloom filter 2^m with m
ranging btw 2..20 only and also the number of hashing functions k to range
btw 1..8 only.

With this current setup for the maximum allowed values the bloom filter can
accommodate for an optimum error positive rate 90852 keys in the bloom
filter only:
8 = 2^20 / 90852 *ln2

Can the values for k and m be bigger?
Right now, in the code it does not accept bigger values than the ones I
specified before.

How can the bloom filter accommodate a large number of keys with low error
rate if m can only go up to 20? This limits the number of keys to 2^20. What
is I need to bloom filter more than 10^6 keys?

Are these 2 restrictions on k and m due to the hash functions implementation
in class KeySelector? If yes can you please let me know a bloom filter
solution that accepts any values for k and m so that it can accommodate any
number of keys for any error rate?

Also, the code in the KeySelector class that generates for a given key the k
hash values is not very documented. I do not understand how the hash
functions are computed on the input key. More exactly, what is the strategy
of selecting the set of *distinct* bits from the key for each hash function
to generate its hash value. I'd appreciate any help or more comments on this
section too.


Thanks!
-- 
.uci