bf::basic_bloom_filter Class Reference

The basic Bloom filter. More...

#include <basic.h>

Inheritance diagram for bf::basic_bloom_filter:

Public Member Functions
	basic_bloom_filter (hasher h, size_t cells)
	Constructs a basic Bloom filter. More...
	basic_bloom_filter (double fp, size_t capacity, size_t seed=0, bool double_hashing=true)
	Constructs a basic Bloom filter by given a desired false-positive probability and an expected number of elements. More...
	basic_bloom_filter (basic_bloom_filter &&)
virtual void	add (object const &o) override
	Adds an element to the Bloom filter. More...
virtual size_t	lookup (object const &o) const override
	Retrieves the count of an element. More...
virtual void	clear () override
	Removes all items from the Bloom filter.
void	remove (object const &o)
	Removes an object from the Bloom filter. More...
void	swap (basic_bloom_filter &other)
	Swaps two basic Bloom filters. More...
Public Member Functions inherited from bf::bloom_filter
template<typename T >
void	add (T const &x)
	Adds an element to the Bloom filter. More...
template<typename T >
size_t	lookup (T const &x) const
	Retrieves the count of an element. More...

Static Public Member Functions
static size_t	m (double fp, size_t capacity)
	Computes the number of cells based on a false-positive rate and capacity. More...
static size_t	k (size_t cells, size_t capacity)
	Computes \(k^*\), the optimal number of hash functions for a given Bloom filter size (in terms of cells) and capacity. More...

Private Attributes
hasher	hasher_
bitvector	bits_

Detailed Description

The basic Bloom filter.

Note

This Bloom filter does not use partitioning because it results in slightly worse performance because partitioned Bloom filters tend to have more 1s than non-partitioned filters.

Definition at line 16 of file basic.h.

Constructor & Destructor Documentation

bf::basic_bloom_filter::basic_bloom_filter	(	hasher	h,
		size_t	cells
	)

Constructs a basic Bloom filter.

Parameters

hasher	The hasher to use.
cells	The number of cells in the bit vector.

Definition at line 19 of file basic.cc.

bf::basic_bloom_filter::basic_bloom_filter	(	double	fp,
		size_t	capacity,
		size_t	seed = 0,
		bool	double_hashing = true
	)

Constructs a basic Bloom filter by given a desired false-positive probability and an expected number of elements.

The implementation computes the optimal number of hash function and required space.

Parameters

fp	The desired false-positive probability.
capacity	The desired false-positive probability.
seed	The initial seed used to construct the hash functions.
double_hashing	Flag indicating whether to use default or double hashing.

Definition at line 25 of file basic.cc.

References k(), m(), and bf::bitvector::resize().

Here is the call graph for this function:

Member Function Documentation

void bf::basic_bloom_filter::add ( object const &  o )

overridevirtual

Adds an element to the Bloom filter.

Parameters

o	A wrapped object.

Implements bf::bloom_filter.

Definition at line 40 of file basic.cc.

References bf::bitvector::set(), and bf::bitvector::size().

Here is the call graph for this function:

size_t bf::basic_bloom_filter::k ( size_t  cells, size_t  capacity  )

static

Computes \(k^*\), the optimal number of hash functions for a given Bloom filter size (in terms of cells) and capacity.

Parameters

cells	The number of cells in the Bloom filter (aka. m)
capacity	The maximum number of elements that can guarantee fp.

Returns

The optimal number of hash functions for cells and capacity.

Definition at line 13 of file basic.cc.

Referenced by basic_bloom_filter().

Here is the caller graph for this function:

size_t bf::basic_bloom_filter::lookup ( object const &  o ) const

overridevirtual

Retrieves the count of an element.

Parameters

o	A wrapped object.

Returns

A frequency estimate for o.

Implements bf::bloom_filter.

Definition at line 46 of file basic.cc.

References bf::bitvector::size().

Here is the call graph for this function:

size_t bf::basic_bloom_filter::m ( double  fp, size_t  capacity  )

static

Computes the number of cells based on a false-positive rate and capacity.

Parameters

fp	The desired false-positive rate
capacity	The maximum number of items.

Returns

The number of cells to use that guarantee fp for capacity elements.

Definition at line 7 of file basic.cc.

Referenced by basic_bloom_filter().

Here is the caller graph for this function:

void bf::basic_bloom_filter::remove

(

object const &

o

)

Removes an object from the Bloom filter.

May introduce false negatives because the bitvector indices of the object to remove may be shared with other objects.

Parameters

o	The object to remove.

Definition at line 59 of file basic.cc.

References bf::bitvector::reset(), and bf::bitvector::size().

Here is the call graph for this function:

void bf::basic_bloom_filter::swap

(

basic_bloom_filter &

other

)

Swaps two basic Bloom filters.

Parameters

other

The other basic Bloom filter.

Definition at line 65 of file basic.cc.

---

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

• basic.h
• basic.cc