bf::a2< Core > Class Template Reference

The \(A^2\) Bloom filter. More...

#include <bloom_filter_a2.h>

Inheritance diagram for bf::a2< Core >:

List of all members.

Public Types
typedef Core	core_type
Public Member Functions
	a2 (core_type &&core, size_t capacity=0)
	Create an \(A^2\) Bloom filter.
template<typename T >
void	add (const T &x)
	Add an item to the set.
template<typename T >
void	remove (const T &x)
	Remove an item from the set.
template<typename T >
unsigned	count (const T &x) const
	Get the count of an item.
const core_type &	core1 () const
	Get the first core.
const core_type &	core2 () const
	Get the second core.
void	clear ()
	Clear all bits.
std::string	to_string () const
	Get a string representation of the Bloom filter.
Static Public Member Functions
static double	k (double f)
	Compute \(k^*\), the optimal number of hash functions for a given false positive rate \(f\).
static double	capacity (unsigned k, unsigned m)
	Compute the capacity of a Bloom filter with respect to a given number of hash functions and number of cells in the store.
Private Attributes
std::size_t	items_
	Number of items in the first (active) core.
std::size_t	capacity_
	Maximum number of items in the first core.
core_type	core1_
core_type	core2_

---

Detailed Description

template<typename Core = core<>>
class bf::a2< Core >

The \(A^2\) Bloom filter.

Definition at line 17 of file bloom_filter_a2.h.

---

Constructor & Destructor Documentation

template<typename Core = core<>>

bf::a2< Core >::a2	(	core_type &&	core,
		size_t	capacity = 0
	)		[inline]

Create an \(A^2\) Bloom filter.

Parameters:

core1	An rvalue reference to one core.
capacity	The capacity of a core. The default value of 0 results in a capacity value that is derived from a false positive probability of 1%.

Todo:

Find a good minimum capacity value when the auto-calculation computes a value that is close to 0.

Definition at line 50 of file bloom_filter_a2.h.

References bf::a2< Core >::capacity(), and bf::a2< Core >::capacity_.

Here is the call graph for this function:

---

Member Function Documentation

template<typename Core = core<>>

template<typename T >

void bf::a2< Core >::add

(

const T &

x

)

[inline]

Add an item to the set.

Template Parameters:

T	The type of the item to insert.

Parameters:

x	An instance of type T.

Reimplemented from bf::bloom_filter< a2< Core > >.

Definition at line 75 of file bloom_filter_a2.h.

template<typename Core = core<>>

static double bf::a2< Core >::capacity	(	unsigned	k,
		unsigned	m
	)		[inline, static]

Compute the capacity of a Bloom filter with respect to a given number of hash functions and number of cells in the store.

The capacity is defined as the maximum number of items the Bloom filter can hold before the FP rate can no longer be guaranteed.

Parameters:

k	The number of hash functions.
m	The number of cells in the Bloom filter

Returns:

The maximum number of items the Bloom filter can hold.

Definition at line 38 of file bloom_filter_a2.h.

Referenced by bf::a2< Core >::a2().

Here is the caller graph for this function:

template<typename Core = core<>>

const core_type& bf::a2< Core >::core1

(

)

const [inline]

Get the first core.

Returns:

A reference to the first core.

Definition at line 112 of file bloom_filter_a2.h.

template<typename Core = core<>>

const core_type& bf::a2< Core >::core2

(

)

const [inline]

Get the second core.

Returns:

A reference to the second core.

Definition at line 119 of file bloom_filter_a2.h.

template<typename Core = core<>>

template<typename T >

unsigned bf::a2< Core >::count

(

const T &

x

)

const [inline]

Get the count of an item.

Template Parameters:

T	The type of the item to query.

Parameters:

x	An instance of type T.

Returns:

A frequency estimate for x.

Reimplemented from bf::bloom_filter< a2< Core > >.

Definition at line 99 of file bloom_filter_a2.h.

template<typename Core = core<>>

static double bf::a2< Core >::k

(

double

f

)

[inline, static]

Compute \(k^*\), the optimal number of hash functions for a given false positive rate \(f\).

Returns:

The optimal number of hash functions.

Definition at line 26 of file bloom_filter_a2.h.

template<typename Core = core<>>

template<typename T >

void bf::a2< Core >::remove

(

const T &

x

)

Remove an item from the set.

Template Parameters:

T	The type of the item to delete.

Parameters:

x	An instance of type T.

Reimplemented from bf::bloom_filter< a2< Core > >.

template<typename Core = core<>>

std::string bf::a2< Core >::to_string

(

)

const [inline]

Get a string representation of the Bloom filter.

Returns:

A string representing of the Bloom filter.

Reimplemented from bf::bloom_filter< a2< Core > >.

Definition at line 131 of file bloom_filter_a2.h.

---

The documentation for this class was generated from the following file:

• bloom_filter_a2.h