Phil Endecott-48 wrote:

There is still no "adaptor" functionality, so I can't mmap() a file to use as the bloom filter's raw content, as I might want to do for e.g. a spellcheck, URL blocklist, etc. etc.

Could you describe this is more detail? I am familiar with the mmap() interface, but how would one go about providing an adaptor so that mmap() could be used as the Bloom filter's raw content? Would this be accomplished through a constructor, for example: // dynamic_basic_bloom_filter(void *addr, const size_t len); dynamic_basic_bloom_filter<std::string> bloom(address, length); Would you happen to know if there is any work being done on a Boost.Posix or any similar C++ project? Phil Endecott-48 wrote:

data() returns a std::bitset, but that doesn't provide access to its data in a form that I can write to a file (e.g. in preparing the data for the above examples). I consider this a fault of std::bitset. I believe you should use a std::vector or array instead.

data() returns the underlying type in each case. For the basic Bloom filter, this is a bitset (std:: or dynamic), and for counting Bloom filters, this is either a boost::array or an std::vector. I see the problem with std::bitset now. In order to serialize the bitset, it would take O(num_bits) operations, rather than the number of blocks (using operator[]). Using an std::vector, the serialization can be accomplished in O(num_elements). It also helps that boost.Serialization provides an implementation for std::vector. Thank you for the insight. I'll work on converting the underlying storage type next week. Phil Endecott-48 wrote:

I see that you still have intersection without discussing the error rate implications.

I will add a section in the tutorial that discusses the implications of union/intersect operations. Phil Endecott-48 wrote:

Your dynamic_bitset has a resize() method. Was that there before? I don't understand how it can work in any useful way.

Yes, this was there initially. The dynamic_basic_bloom_filter is the only dynamic Bloom filter that has the resize() method. I intend to remove this method, as users requiring a resize can instantiate a new dynamic Bloom filter to achieve the same effect. It was a design relic that should've been discarded much sooner, as it is more dangerous to users than useful. Phil Endecott-48 wrote:

The final documentation should mention the complexity of each method.

I've made sure to include the complexity of all methods. This is located at: http://svn.boost.org/svn/boost/sandbox/bloom_filter/trunk/libs/bloom_filter/... In the class references, do you think it would be convenient to make each function name clickable and make them link to the specific entry in the function reference? Thank you, -Alej -- View this message in context: http://boost.2283326.n4.nabble.com/Feedback-Towards-a-Better-Boost-BloomFilt... Sent from the Boost - Dev mailing list archive at Nabble.com.

Alejandro Cabrera wrote:

Phil Endecott-48 wrote:

...

There is still no "adaptor" functionality, so I can't mmap() a file to use as the bloom filter's raw content, as I might want to do for e.g. a spellcheck, URL blocklist, etc. etc.

Could you describe this is more detail? I am familiar with the mmap() interface, but how would one go about providing an adaptor so that mmap() could be used as the Bloom filter's raw content? Would this be accomplished through a constructor, for example:

// dynamic_basic_bloom_filter(void *addr, const size_t len); dynamic_basic_bloom_filter<std::string> bloom(address, length);

It is normally preferable to pass a begin-end pair rather than address and length, but fundamentally yes I would like to be able to construct a read-only bloom filter from a pair of const_iterators i.e. const pointers in this case.

Would you happen to know if there is any work being done on a Boost.Posix or any similar C++ project?

Not relevant.

Phil Endecott-48 wrote:

...

data() returns a std::bitset, but that doesn't provide access to its data in a form that I can write to a file (e.g. in preparing the data for the above examples). I consider this a fault of std::bitset. I believe you should use a std::vector or array instead.

data() returns the underlying type in each case. For the basic Bloom filter, this is a bitset (std:: or dynamic), and for counting Bloom filters, this is either a boost::array or an std::vector.

I see the problem with std::bitset now. In order to serialize the bitset, it would take O(num_bits) operations, rather than the number of blocks (using operator[]). Using an std::vector, the serialization can be accomplished in O(num_elements). It also helps that boost.Serialization provides an implementation for std::vector. Thank you for the insight. I'll work on converting the underlying storage type next week.

I don't care about serialisation. I just want to be able to const T* p = &(*(bloom_filter.data().begin())); size_t len = sizeof(T) * bloom_filter.data().size(); write(fd,p,len); Regards, Phil.

Alejandro Cabrera wrote:

Phil,

Phil Endecott-48 wrote:

...

It is normally preferable to pass a begin-end pair rather than address and length, but fundamentally yes I would like to be able to construct a read-only bloom filter from a pair of const_iterators i.e. const pointers in this case.

The input iterator constructor is already available.

No, I don't think so. What you have is a ctor that iterates over a sequence of values and inserts them: template <typename InputIterator> basic_bloom_filter(const InputIterator start, const InputIterator end) { for (InputIterator i = start; i != end; ++i) this->insert(*i); } What I want is a way to adapt a chunk of raw memory, which I've got from mmap(), and to treat it as a bloom filter. I haven't yet seen any "adaptor" functionality in your code.

All that remains is what you describe below.

Phil Endecott-48 wrote:

...

I don't care about serialisation. I just want to be able to

const T* p = &(*(bloom_filter.data().begin())); size_t len = sizeof(T) * bloom_filter.data().size(); write(fd,p,len);

Regards, Phil.

All this should take is changing the underlying storage type to something that supports the operations begin() and size(). The intent is to use std::vector, as with the dynamic counting Bloom filter implementations. The operations you've described above are serialization. This will be supported soon, as soon as I can work on the basic Bloom filters. I'll add a test to my suite to make sure there is a way to support this in both directions (write/read, store/load).

I really don't want to "load" the filter i.e. to do something that needs O(N) time and O(N) memory. I just want to mmap the file into memory and "declare" the bloom filter into existence in O(1) time. Then when I eventually use it, pages will be faulted-in on demand. The aim is to ensure that I can have a perhaps very large filter and yet to perform small numbers of queries quite quickly. Regards, Phil.