Re: [boost] [GSoC] Request for Feedback on Boost.Bloom Filter Project

Subject: Re: [boost] [GSoC] Request for Feedback on Boost.Bloom Filter Project
From: Arash Partow (arash_at_[hidden])
Date: 2011-06-25 03:49:07

On 21/06/2011 2:21 PM, Alejandro Cabrera wrote:
> Hello all,
>
> I'm writing to request feedback, suggestions, and advice from the Boost community. I've been working on a Bloom filter data structure for about a month and a half now. At this point, the following is complete and available in the Boost Sandbox:
> - working, basic prototype (insert & query operations, union & intersect)
> - a test suite covering the public interface
> - five examples
> - documentation covering many aspects of the project (tested on Chrome 12 and 13, Firefox 4 and 6)
>

One more suggestion, have you considered introducing a compression function/method? Compression wrt BF is really just super-imposing (Or'ing) the 1st half of the BF with the second half and halving the quantization factor for the hash values, this operation doubles the effective false positive probability.

This technique is typically used in DHT scenarios. where the complete BF is stored at a particular node, then a compressed version is sent to the direct neighbors of that node, which they then compress the received BF again and send that onto their direct neighbors etc, until such time as the BF reaches a certain size or the EFPP is above a certain threshold. (the BF is coupled with information regarding routing to the originating node)