hadoop-common-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stu Hood (JIRA)" <j...@apache.org>
Subject [jira] Created: (HADOOP-2654) CountingBloomFilter can overflow its storage
Date Fri, 18 Jan 2008 07:15:33 GMT
CountingBloomFilter can overflow its storage
--------------------------------------------

                 Key: HADOOP-2654
                 URL: https://issues.apache.org/jira/browse/HADOOP-2654
             Project: Hadoop
          Issue Type: Bug
          Components: contrib/hbase
            Reporter: Stu Hood


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.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message