Mailing-List: contact dev-help@hbase.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@hbase.apache.org
Received-SPF: neutral (athena.apache.org: local policy)
MIME-Version: 1.0
In-Reply-To: <525EB08B-7390-409F-A77B-BC35FF90D7E4@TheFacebook.com>
References: <AANLkTikoJ1jBbdwrWHeHOBkt3npep=YvGQKuYw3oFzdv@mail.gmail.com>
 <525EB08B-7390-409F-A77B-BC35FF90D7E4@TheFacebook.com>
From: Ted Dunning <tdunning@maprtech.com>
Date: Tue, 25 Jan 2011 09:31:00 -0800
Message-ID: <AANLkTimycKU+2Gc9Uez-q8Kn7xxhOTTM7p1Tx2KvQare@mail.gmail.com>
Subject: Re: Overhead of Bloomfilters
To: dev@hbase.apache.org
Content-Type: multipart/alternative; boundary=0016e64cbb30b548db049aaf1528

--0016e64cbb30b548db049aaf1528
Content-Type: text/plain; charset=ISO-8859-1

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

On Tue, Jan 25, 2011 at 8:11 AM, Nicolas Spiegelberg <nspiegelberg@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" <lars.george@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
>

--0016e64cbb30b548db049aaf1528--