40 MiB for ten million users? I think you should ditch the bloom filter if the false-positive rate is set so low it takes that much space. Assuming you can map

40 MiB for ten million users? I think you should ditch the bloom filter if the false-positive rate is set so low it takes that much space. Assuming you can map phone numbers onto the integers from 0 to ten billion, trivial compression of the is-a-user/is-not-a-user bit sequence should easily fit in ~14MiB [1]. See also: succinct data structures [2] for accessing data without decompressing it. (This is obviously a short term solution. Growth will overcome the savings.) 1: http://www.wolframalpha.com/input/?i=%28-p+lg_2%28p%29-%281-p%29+lg_2%281-p%29%29+*+ten+billion++%2F+2^23+where++p+%3D+ten+million+%2F+ten+billion http://www.wolframalpha.com/input/?i=%28-p+lg_2%28p%29-%281-... 2: http://en.wikipedia.org/wiki/Succinct_data_structure http://en.wikipedia.org/wiki/Succinct_data_structure