fc::bloom_parameters Class Reference

#include <bloom_filter.hpp>

Collaboration diagram for fc::bloom_parameters:

Classes
struct	optimal_parameters_t

Public Member Functions
	bloom_parameters ()
virtual	~bloom_parameters ()
bool	operator! ()
virtual bool	compute_optimal_parameters ()

Public Attributes
unsigned long long int	minimum_size
unsigned long long int	maximum_size
unsigned int	minimum_number_of_hashes
unsigned int	maximum_number_of_hashes
unsigned long long int	projected_element_count
double	false_positive_probability
unsigned long long int	random_seed
optimal_parameters_t	optimal_parameters

Detailed Description

Definition at line 46 of file bloom_filter.hpp.

Constructor & Destructor Documentation

bloom_parameters()

fc::bloom_parameters::bloom_parameters ( )

inline

Definition at line 50 of file bloom_filter.hpp.

   : minimum_size(1),
     maximum_size(std::numeric_limits<unsigned long long int>::max()),
     minimum_number_of_hashes(1),
     maximum_number_of_hashes(std::numeric_limits<unsigned int>::max()),
     projected_element_count(10000),
     false_positive_probability(1.0 / projected_element_count),
     random_seed(0xA5A5A5A55A5A5A5AULL)
   {}

~bloom_parameters()

virtual fc::bloom_parameters::~bloom_parameters ( )

inlinevirtual

Definition at line 60 of file bloom_filter.hpp.

   {}

Member Function Documentation

compute_optimal_parameters()

virtual bool fc::bloom_parameters::compute_optimal_parameters ( )

inlinevirtual

Definition at line 109 of file bloom_filter.hpp.

   {
      /*
        Note:
        The following will attempt to find the number of hash functions
        and minimum amount of storage bits required to construct a bloom
        filter consistent with the user defined false positive probability
        and estimated element insertion count.
      */
 
      if (!(*this))
         return false;
 
      double min_m = std::numeric_limits<double>::infinity();
      double min_k = 0.0;
      double curr_m = 0.0;
      double k = 1.0;
 
      while (k < 1000.0)
      {
         double numerator   = (- k * projected_element_count);
         double denominator = std::log(1.0 - std::pow(false_positive_probability, 1.0 / k));
         curr_m = numerator / denominator;
         if (curr_m < min_m)
         {
            min_m = curr_m;
            min_k = k;
         }
         k += 1.0;
      }
 
      optimal_parameters_t& optp = optimal_parameters;
 
      optp.number_of_hashes = static_cast<unsigned int>(min_k);
      optp.table_size = static_cast<unsigned long long int>(min_m);
      optp.table_size += (((optp.table_size % bits_per_char) != 0) ? (bits_per_char - (optp.table_size % bits_per_char)) : 0);
 
      if (optp.number_of_hashes < minimum_number_of_hashes)
         optp.number_of_hashes = minimum_number_of_hashes;
      else if (optp.number_of_hashes > maximum_number_of_hashes)
         optp.number_of_hashes = maximum_number_of_hashes;
 
      if (optp.table_size < minimum_size)
         optp.table_size = minimum_size;
      else if (optp.table_size > maximum_size)
         optp.table_size = maximum_size;
 
      return true;
   }

operator!()

bool fc::bloom_parameters::operator! ( )

inline

Definition at line 63 of file bloom_filter.hpp.

   {
      return (minimum_size > maximum_size)      ||
             (minimum_number_of_hashes > maximum_number_of_hashes) ||
             (minimum_number_of_hashes < 1)     ||
             (0 == maximum_number_of_hashes)    ||
             (0 == projected_element_count)     ||
             (false_positive_probability < 0.0) ||
             (std::numeric_limits<double>::infinity() == std::abs(false_positive_probability)) ||
             (0 == random_seed)                 ||
             (0xFFFFFFFFFFFFFFFFULL == random_seed);
   }

Member Data Documentation

false_positive_probability

double fc::bloom_parameters::false_positive_probability

Definition at line 92 of file bloom_filter.hpp.

maximum_number_of_hashes

unsigned int fc::bloom_parameters::maximum_number_of_hashes

Definition at line 82 of file bloom_filter.hpp.

maximum_size

unsigned long long int fc::bloom_parameters::maximum_size

Definition at line 78 of file bloom_filter.hpp.

minimum_number_of_hashes

unsigned int fc::bloom_parameters::minimum_number_of_hashes

Definition at line 81 of file bloom_filter.hpp.

minimum_size

unsigned long long int fc::bloom_parameters::minimum_size

Definition at line 77 of file bloom_filter.hpp.

optimal_parameters

optimal_parameters_t fc::bloom_parameters::optimal_parameters

Definition at line 107 of file bloom_filter.hpp.

projected_element_count

unsigned long long int fc::bloom_parameters::projected_element_count

Definition at line 87 of file bloom_filter.hpp.

random_seed

unsigned long long int fc::bloom_parameters::random_seed

Definition at line 94 of file bloom_filter.hpp.

---

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

• libraries/fc/include/fc/bloom_filter.hpp