Boost logo

Boost :

Subject: Re: [boost] Boost.Bloom_filter now in Sandbox (WAS Re: Interest in a Bloom Filter?)
From: Milosz Marian HULBOJ (mhulboj_at_[hidden])
Date: 2009-06-18 05:01:56


> The idea of the bloom_filter is to provide precisely that, a bloom
> filter -- any compression you might want to do in transmitting a
> bloom_filter would IMO be beyond the scope of the library. There has
> been some suggestions of implementing a compressed_bloom_filter that
> maintains a compressed bitset, but afar from that I must say I have no
> idea what self superimposed compression mode.

Implementing naïve bloom filter according to the encyclopædic definition
does not make much sense. It will be just a proof of concept... As I
have already mentioned in the other thread
(http://thread.gmane.org/gmane.comp.lib.boost.devel/190192/)
it's all about providing a generic solution that could accommodate all
the peculiarities.

In my opinion there is some established research on compressed bloom
filters and that the issue of the compression is not orthogonal to the
bloom filter itself.

I also agree that it is a must to provide the way to determine optimal
parameter values for all the variants of the filters.

As for the erasure, I think that Arash was referring to cropped filters
and interpretation as erasure codes. (reference: Bloom Filters: One Size
Fits All?)

Regards,
Milosz


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk