Re: [boost] Interest in a Bloom Filter?

Subject: Re: [boost] Interest in a Bloom Filter?
From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2009-06-08 02:31:58

Hi Jeffrey,

On Mon, Jun 8, 2009 at 2:00 PM, Jeffrey Bosboom<jbosboom_at_[hidden]> wrote:
> Dean Michael Berris wrote:
>>
>> During the weekend, I got acquainted with and excited about Bloom
>> Filters and the utility of such a data structure.
>
> I've only heard of bloom effects as used in 3D graphics for more realistic
> lighting effects. Â Looking at the code, that does not seem to be the purpose
> of your bloom filter. Â Just what is it and why might I use it?
>

A Bloom Filter is a space efficient data-structure that allows you to
represent set membership that allows for false positives (elements may
have been marked as included in a set when they really aren't part of
the set) but not false negatives (when an element has not been
included/added in the set, the bloom filter wouldn't show that they
are part of the set). These have been used in proxy caches to signify
whether they already have a cached copy of a URI. File systems also
use these to see whether a part of a file (or a page) has already been
accessed before (to limit the frequency of fetching pages that have
been fetched before on a DFS for instance).

A more in-depth explanation of bloom filters can be found here:
http://en.wikipedia.org/wiki/Bloom_filter

HTH

-- 
Dean Michael Berris | Software Engineer, Friendster, Inc.
blog.cplusplus-soup.com | twitter.com/mikhailberis |
linkedin.com/in/mikhailberis | profiles.friendster.com/mikhailberis |
deanberris.com