[HBASE-19] CountingBloomFilter can overflow its storage

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 0.2.0
• Assignee: Unassigned
• Reporter: Stu Hood
• Created: 18/Jan/08 07:13
• Updated: 22/Aug/08 21:13
• Resolved: 07/Feb/08 20:11

Description

The org.onelab.filter.CountingBloomFilter implementation does not check the value of a bucket before incrementing/decrementing it. The buckets in a Counting Bloom filter must not be allowed to overflow, and if they reach their maximum value, they must not be allowed to decrement. This is the only way to preserve the assumptions of the filter (without larger buckets). See: http://en.wikipedia.org/wiki/Bloom_filter#Counting_filters

Currently, if enough values hash to a bucket, the CountingBloomFilter may begin reporting false negatives when it wraps back around to 0.