4 ms·
The Add() function has to account for the possibility of the count potentially exceeding the maximum counter value. In this case, there’s not much we can do exc
by panic 9y ago
The Add() function has to account for the possibility of the count potentially exceeding the maximum counter value. In this case, there’s not much we can do except avoid an increment and flag the filter data as potentially erroneous.
Most counting bloom filters handle this situation by using saturating arithmetic: once the count hits the maximum, it remains stuck there, never decrementing again until the filter is completely cleared (see WebKit's implementation, for example: https://github.com/WebKit/webkit/blob/master/Source/WTF/wtf/BloomFilter.h#L228-L231 https://github.com/WebKit/webkit/blob/master/Source/WTF/wtf/...). This maintains the Bloom Filter Guarantee™ that you can get false positives but never false negatives.
- stormbeard 9y agoThat's actually a good solution for the problem I had with the false negatives. I'm glad other folks figured that out.
- pzh 9y agoWouldn't that only work if you only remove stuff that you already added, i.e. you can't remove an element that would be considered a 'false positive' and still expect to have no 'false negatives' after that?
- stormbeard 9y agoRight, but I think they mean for that particular cause of false negatives quoted (counter overflow). There's no good way I can think of to mitigate the false negatives caused by removing items never inserted into the filter since you have no way of knowing what was exactly added and what wasnt. There's a paper linked in the blog post that goes into a lot of detail about minimizing false negative probability.