Bloom Filters

Detailed Description

Bloom filters are a probabilistic data-structure useful to conservatively represent membership in a set using less than 1 bit per item.

Classes
struct	nvbio::inplace_or< T >
struct	nvbio::inplace_or< uint32 >
struct	nvbio::inplace_or< uint2 >
struct	nvbio::inplace_or< uint4 >
struct	nvbio::inplace_or< uint64 >
struct	nvbio::inplace_or< uint64_2 >
struct	nvbio::inplace_or< uint64_4 >
struct	nvbio::bloom_filter< K, Hash1, Hash2, Iterator, OrOperator >
struct	nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >

Functions
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	nvbio::optimal_bloom_filter_hashes (const float bits_per_key)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE float	nvbio::optimal_bloom_filter_bits_per_key (const float fp_rate)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE float	nvbio::optimal_bloom_filter_bits_per_key (const uint32 K)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::optimal_bloom_filter_parameters (const float fp_rate, uint32 *K, float *bits_per_key)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE float	nvbio::optimal_bloom_filter_fp_rate (const uint32 K, const float bits_per_key)

Function Documentation

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE float nvbio::optimal_bloom_filter_bits_per_key

(

const float

fp_rate)

compute the optimal Bloom filter size for a given target false positive rate, assuming an optimal number of hash functions

Definition at line 387 of file bloom_filter.h.

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE float nvbio::optimal_bloom_filter_bits_per_key

(

const uint32

K)

compute the optimal Bloom filter size for a given number of hash functions

Definition at line 395 of file bloom_filter.h.

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE float nvbio::optimal_bloom_filter_fp_rate	(	const uint32	K,
		const float	bits_per_key
	)

compute the achievable false positive rate of a Bloom filter with a given number of hash functions and bits per key

Definition at line 415 of file bloom_filter.h.

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::optimal_bloom_filter_hashes

(

const float

bits_per_key)

compute the optimal number of Bloom filter hash functions given the number of bits per key

Definition at line 378 of file bloom_filter.h.

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void nvbio::optimal_bloom_filter_parameters	(	const float	fp_rate,
		uint32 *	K,
		float *	bits_per_key
	)

compute the optimal Bloom filter parameters for a given target false positive rate, specifically the number of hash functions K, and the number of bits per key

Definition at line 404 of file bloom_filter.h.