New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

False negative in Counting Bloom #16

Closed

richardstartin opened this issue Dec 27, 2019 · 1 comment

Collaborator

richardstartin commented Dec 27, 2019 •

edited

Loading

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

Contributor

thomasmueller commented Dec 27, 2019

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).

thomasmueller closed this as completed

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment