Re: [boost] Interest in a Bloom Filter?

Subject: Re: [boost] Interest in a Bloom Filter?
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2009-06-08 02:47:04

Dean Michael Berris <mikhailberis <at> gmail.com> writes:

> 
> Hi Everyone,
> 
> During the weekend, I got acquainted with and excited about Bloom
> Filters and the utility of such a data structure. I then proceeded to
> look at generic implementations of a bloom filter and I thought about
> implementing one myself instead as a simple exercise.
> 
> Attached is what I came up with which I'm submitting as a library for
> review (and uploading to the vault). Also attached is a sample program
> which uses the bloom_filter.

I'm definitely interested in having a Bloom filter in
Boost.

A couple of comments on your current implementation:

* Seems to me it is more natural (or at least more in sync
with current custom in std containers) to let the order of
bloom_filter template parameters be

  Input,M,K

* Why not make bloom_filter<M,K,T> interface mimic that
of a std::map<T,bool> so that instead of

  bf.contains(x)

one can write

  bf[x] // returns a bool

Admittedly, one cannot extend this analogy to insertion:
bf[x]=true could represent bf.insert(x), but bf[x]=false
is not implementable due to the very nature of Bloom
filters.

* Again with the purpose of using as standard a
terminology as possible I'd rename reset() to clear().

* state() should return a const reference to bit_set so
as to avoid copying when not strictly needed.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo