NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Functions
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.