You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@hbase.apache.org by Lars George <la...@gmail.com> on 2011/01/25 15:22:17 UTC

Overhead of Bloomfilters

Hi,

(Probably aimed at Nicolas)

Do we have a (rough) formula of overhead, i.e. the size of the
bloomfilters for row and col granularity as for example depending on
the KV count and average sizes (as reported by the HFile main()
helper)?

Thanks,
Lars

Re: Overhead of Bloomfilters

Posted by Ted Dunning <td...@maprtech.com>.

See http://en.wikipedia.org/wiki/Double_hashing for information on double
hashing.

On Tue, Jan 25, 2011 at 8:11 AM, Nicolas Spiegelberg <ns...@fb.com>wrote:

> A great article for Bloom Filter rules of thumb:
>
> http://corte.si/posts/code/bloom-filter-rules-of-thumb/
>
> Note that only rules #1 & #2 apply for our use case. Rule #3, while true,
> isn't as big a worry because we use combinatorial generation for hashes, so
> the number of 'expensive' hash calculations is 2, no matter how many hash
> functions need to be generated.   Note that this drastically (400%+) sped up
> our BloomFilter.add() speed.
>
> Sent from my iPhone
>
> On Jan 25, 2011, at 6:22 AM, "Lars George" <la...@gmail.com> wrote:
>
> > Hi,
> >
> > (Probably aimed at Nicolas)
> >
> > Do we have a (rough) formula of overhead, i.e. the size of the
> > bloomfilters for row and col granularity as for example depending on
> > the KV count and average sizes (as reported by the HFile main()
> > helper)?
> >
> > Thanks,
> > Lars
>

Re: Overhead of Bloomfilters

Posted by Lars George <la...@gmail.com>.

Thanks Nicolas,

I was after the actual size of it though, I assume you have no
disclosable numbers? Just curious.If not I guess the best is to run a
YSCB! or even PE to load a BF enables table and then check the HFile
output? Does that print the BF sizes too?

Lars

On Tue, Jan 25, 2011 at 4:11 PM, Nicolas Spiegelberg
<ns...@fb.com> wrote:
> A great article for Bloom Filter rules of thumb:
>
> http://corte.si/posts/code/bloom-filter-rules-of-thumb/
>
> Note that only rules #1 & #2 apply for our use case. Rule #3, while true, isn't as big a worry because we use combinatorial generation for hashes, so the number of 'expensive' hash calculations is 2, no matter how many hash functions need to be generated.   Note that this drastically (400%+) sped up our BloomFilter.add() speed.
>
> Sent from my iPhone
>
> On Jan 25, 2011, at 6:22 AM, "Lars George" <la...@gmail.com> wrote:
>
>> Hi,
>>
>> (Probably aimed at Nicolas)
>>
>> Do we have a (rough) formula of overhead, i.e. the size of the
>> bloomfilters for row and col granularity as for example depending on
>> the KV count and average sizes (as reported by the HFile main()
>> helper)?
>>
>> Thanks,
>> Lars
>

Re: Overhead of Bloomfilters

Posted by Nicolas Spiegelberg <ns...@fb.com>.

A great article for Bloom Filter rules of thumb:

http://corte.si/posts/code/bloom-filter-rules-of-thumb/

Note that only rules #1 & #2 apply for our use case. Rule #3, while true, isn't as big a worry because we use combinatorial generation for hashes, so the number of 'expensive' hash calculations is 2, no matter how many hash functions need to be generated.   Note that this drastically (400%+) sped up our BloomFilter.add() speed. 

Sent from my iPhone

On Jan 25, 2011, at 6:22 AM, "Lars George" <la...@gmail.com> wrote:

> Hi,
> 
> (Probably aimed at Nicolas)
> 
> Do we have a (rough) formula of overhead, i.e. the size of the
> bloomfilters for row and col granularity as for example depending on
> the KV count and average sizes (as reported by the HFile main()
> helper)?
> 
> Thanks,
> Lars