{"action":"opened","issue":{"url":"https://api.github.com/repos/vagnerclementino/guava/issues/27","repository_url":"https://api.github.com/repos/vagnerclementino/guava","labels_url":"https://api.github.com/repos/vagnerclementino/guava/issues/27/labels{/name}","comments_url":"https://api.github.com/repos/vagnerclementino/guava/issues/27/comments","events_url":"https://api.github.com/repos/vagnerclementino/guava/issues/27/events","html_url":"https://github.com/vagnerclementino/guava/issues/27","id":225265651,"number":27,"title":"Bloom Filter Accuracy Degrades At Small Expected Number of Insertions","user":{"login":"vagnerclementino","id":7996131,"avatar_url":"https://avatars3.githubusercontent.com/u/7996131?v=3","gravatar_id":"","url":"https://api.github.com/users/vagnerclementino","html_url":"https://github.com/vagnerclementino","followers_url":"https://api.github.com/users/vagnerclementino/followers","following_url":"https://api.github.com/users/vagnerclementino/following{/other_user}","gists_url":"https://api.github.com/users/vagnerclementino/gists{/gist_id}","starred_url":"https://api.github.com/users/vagnerclementino/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vagnerclementino/subscriptions","organizations_url":"https://api.github.com/users/vagnerclementino/orgs","repos_url":"https://api.github.com/users/vagnerclementino/repos","events_url":"https://api.github.com/users/vagnerclementino/events{/privacy}","received_events_url":"https://api.github.com/users/vagnerclementino/received_events","type":"User","site_admin":false},"labels":[{"id":594614693,"url":"https://api.github.com/repos/vagnerclementino/guava/labels/package:%20hash","name":"package: hash","color":"ededed","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2017-04-29T15:50:46Z","updated_at":"2017-04-29T15:50:46Z","closed_at":null,"body":"Bloom Filters created with less than 500 expected insertions and a fpp of 1e-7 do not achieve that desired false positive probability in practice. This issue is most noticeable at a low number of insertions and slowly disappears as they increase towards 500.\r\n\r\nTesting details:\r\n300,000 random unique strings of length 14 were generated for each test iteration\r\nBloom Filter created using \"Funnels.stringFunnel(StandardCharsets.UTF_8)\"\r\nDesired false positive probability of 1e-7\r\nTested for expected number of insertions from 1 to 2000\r\nEach test rerun multiple times\r\nFirst n strings added to Bloom Filter\r\nEntire string set tested by calling mightContain()\r\nVerified first n were true\r\nCounted how many of the remaining strings returned true\r\n\r\nResults:\r\nAverage number of false positives for 1 insertions was around 5000 (1.6e-2)\r\nAverage number of false positives for 2 insertions was around 1500 (5e-3)\r\nFalse positives dropped to 0 around 500 insertions\r\n\r\nAnalysis:\r\nFor the most drastic case when the number of expected insertions is 1, the number of optimal bits is ~34 and the optimal number of hashes is ~23. A peculiarity of this implementation is that the number of bits actually used is always a multiple of 64, so in this case 64 bits is actually used (see BloomFilterStrategies.java line 48 where the bitSize is set to bits.bitSize() rather than the computed number of bits). This means there is a 1/64 chance that the second hash is a multiple of 64 and hence does not affect the combinedHash when incrementing. When this happens, every bit index computed is the same index. If we take a case where a single insertion flips all 23 bits possible, the probability of a false positive is at least (1/64)*(23/64) = 5.6e-3 regardless of the fpp requested. As the number of expected insertions increases, the number of bits does as well which lessens the chance of a hash producing only 1 unique bit index. Note that this happens for all powers of 2 though (i.e. hashes can produce only 2 unique bit indices, and 4, and so on...).\r\n\r\nReview of the implementation suggests adding the modded hash2 value is not ideal for a \"low\" number of bits. A quick test shows calling the hash a second time (with a hard-coded seed) and adding these two additional values at staggered intervals (e.g. every 2 and every 3 iterations) drastically improves the accuracy at low number of insertions by avoiding such a high chance of so many duplicate indices."}}
{"actor":{"display_login":"vagnerclementino"}}