False negative in Counting Bloom

FastFilter / fastfilter_java

Fast Approximate Membership Filters (Java)

Apache License 2.0

238 stars 27 forks source link

False negative in Counting Bloom #16

Closed richardstartin closed 4 years ago

richardstartin commented 4 years ago

Steps to reproduce:

Hash.setSeed(6360526788365209414L);
long[] keys = new long[] {-4535795219140351433L, 4882771549875911188L, -6502814355560814028L};
int bitsPerKey = 16;
var filter = COUNTING_BLOOM.construct(keys, bitsPerKey);
assertTrue(filter.mayContain(-4535795219140351433L)); // false

thomasmueller commented 4 years ago

The root cause of this is a counter overflow, I created issue #20 to track this.

The regression is fixed, by adding a 64 more bits. But this only fixes a subset of the cases (counting Bloom filters with very few entries).