hbase-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "stack (JIRA)" <j...@apache.org>
Subject [jira] Updated: (HBASE-19) CountingBloomFilter can overflow its storage
Date Thu, 07 Feb 2008 20:13:08 GMT

     [ https://issues.apache.org/jira/browse/HBASE-19?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

stack updated HBASE-19:
-----------------------

    Resolution: Fixed
        Status: Resolved  (was: Patch Available)

Committed.  Thanks Stu (And Bryan for fixing patch to apply in new location).

> CountingBloomFilter can overflow its storage
> --------------------------------------------
>
>                 Key: HBASE-19
>                 URL: https://issues.apache.org/jira/browse/HBASE-19
>             Project: Hadoop HBase
>          Issue Type: Bug
>            Reporter: Stu Hood
>             Fix For: 0.2.0
>
>         Attachments: 19-v2.patch, 19.patch, counting-overflow-fourbit.patch, counting-overflow-fourbit.patch,
counting-overflow.patch
>
>
> 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