bloom_parameters Class Reference

#include <bloom_filter.hpp>

Collaboration diagram for 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 45 of file bloom_filter.hpp.

Constructor & Destructor Documentation

bloom_parameters()

bloom_parameters::bloom_parameters ( )

inline

Definition at line 49 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 bloom_parameters::~bloom_parameters ( )

inlinevirtual

Definition at line 59 of file bloom_filter.hpp.

   {}

Member Function Documentation

compute_optimal_parameters()

virtual bool bloom_parameters::compute_optimal_parameters ( )

inlinevirtual

Definition at line 108 of file bloom_filter.hpp.

References bits_per_char, maximum_number_of_hashes, maximum_size, minimum_number_of_hashes, minimum_size, bloom_parameters::optimal_parameters_t::number_of_hashes, optimal_parameters, projected_element_count, and bloom_parameters::optimal_parameters_t::table_size.

Referenced by main().

   {
      /*
        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 k      = 1.0;

      while (k < 1000.0)
      {
         const double numerator   = (- k * projected_element_count);
         const double denominator = std::log(1.0 - std::pow(false_positive_probability, 1.0 / k));

         const double 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;
   }

Here is the caller graph for this function:

operator!()

bool bloom_parameters::operator! ( )

inline

Definition at line 62 of file bloom_filter.hpp.

References false_positive_probability, maximum_number_of_hashes, maximum_size, minimum_number_of_hashes, minimum_size, projected_element_count, and random_seed.

   {
      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 bloom_parameters::false_positive_probability

Definition at line 91 of file bloom_filter.hpp.

Referenced by main(), and operator!().

maximum_number_of_hashes

unsigned int bloom_parameters::maximum_number_of_hashes

Definition at line 81 of file bloom_filter.hpp.

Referenced by compute_optimal_parameters(), main(), and operator!().

maximum_size

unsigned long long int bloom_parameters::maximum_size

Definition at line 77 of file bloom_filter.hpp.

Referenced by compute_optimal_parameters(), and operator!().

minimum_number_of_hashes

unsigned int bloom_parameters::minimum_number_of_hashes

Definition at line 80 of file bloom_filter.hpp.

Referenced by compute_optimal_parameters(), and operator!().

minimum_size

unsigned long long int bloom_parameters::minimum_size

Definition at line 76 of file bloom_filter.hpp.

Referenced by compute_optimal_parameters(), and operator!().

optimal_parameters

optimal_parameters_t bloom_parameters::optimal_parameters

Definition at line 106 of file bloom_filter.hpp.

Referenced by bloom_filter::bloom_filter(), and compute_optimal_parameters().

projected_element_count

unsigned long long int bloom_parameters::projected_element_count

Definition at line 86 of file bloom_filter.hpp.

Referenced by compute_optimal_parameters(), main(), and operator!().

random_seed

unsigned long long int bloom_parameters::random_seed

Definition at line 93 of file bloom_filter.hpp.

Referenced by main(), and operator!().

---

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

• bloom/bloom_filter.hpp