libBf

libBf is a header-only C++11 library that implements various types of of Bloom filters.

Architecture

libBf implements a variety of different Bloom filters. Each Bloom filter type is based on one or more cores, which is a policy class that captures store, hash, and partition properties.

Store: The store policy abstracts an $O(1)$ random-access array data structure to access counter values.
Hash: The hash policy computes the hash values according to one of three possible schemes. The default scheme is simply to use the hash value of the underlying hasher (which is also configurable). The two other available schemes are double hashing and extended double hashing, implement $k$ independent hash function using only two pairwise independent hash functions of the form
$g_i(x) = h_1(x) + ih_2(x) + f(i) \quad \forall i \in [k]$
The function $f$ is an arbitrary mapping into the real number. For $$f(i) \equiv 0$$ we have double hashing.
Partition: The partition policy determines how to distribute the $k$ hash values to the bit vector. The default policy is to not use partitioning and simply compute $h_i(x) \bmod m$ for all $i \in [k]$ . Alternatively, one could partitioning to map each hash value $h_i(x)$ into a disjoint sub-vector of size $m/k$ , i.e.,
$\left(h_i(x) \bmod \frac{m}{k}\right) + \frac{(i-1)m}{k} \quad \forall i\in[k]$

The Figure below shows the architecture of libBf.

Each Bloom filter implementation in libBf is uses one or more cores. A core
is a policy class that captures the store, hash, and partition properties of
the Bloom filter.

Download

The libBf source code resides at github and ships with a BSD-style licence.

Download
Version: 0.1
Released: May 22, 2011

Usage

For clarity the following discussion assumes that all the libBf classes exist in the global namespace, e.g., by hoisting them via using namespace bf.

Synopsis

Briefly, this is how you get started with libBf:

Define a core type:

typedef core<
  fixed_width<uint8_t, std::allocator<uint8_t>
, double_hashing<default_hasher, 42, 4711>
, no_partitioning
> my_core;

Define a Bloom filter type:
```
typedef basic<my_core> my_bloom_filter;
```
Instantiate with a core:
```
my_bloom_filter bf({ 1 << 10, 5, 4 });
```

Use:

bf.add("foo")
bf.add("foo")
bf.add('z')
bf.add(3.14159)
std::cout << bf.count("foo") << std::endl;  // returns (likely) 2

For a complete documentation of the API, please refer to the Doxygen documentation.