Module bloom

Description
Data Types
Function Index
Function Details

Bloom Filter implementation.

Version: $Id$

Authors: Maik Lange (malange@informatik.hu-berlin.de).

References

A. Broder, M. Mitzenmacher Network Applications of Bloom Filters: A Survey 2004 Internet Mathematics 1(4)

Data Types

key()

key() = any()

Function Index

add/2	Adds one item to the bloom filter.
add_list/2	Adds multiple items to the bloom filter.
calc_FPR/3	Calculates FP for an M-bit large bloom filter with K hash funtions and a maximum number of N elements.
calc_HF_num/2	Calculates optimal number of hash functions for an M-bit large BloomFilter with a maximum of N Elements.
calc_HF_numEx/2	Calculates the optimal number of hash functions for a bloom filter with N elements and a false positive probability FP.
calc_least_size/3	Calculates the number of bits needed by a bloom filter to have a false positive probability of FP using K hash functions and up to N-Elements.
calc_least_size_opt/2	Calculates the number of bits needed by a bloom filter to have a false positive probability of FP using up to N elements and the optimal number of hash functions K = ln(2)*M/N.
equals/2	Checks whether two bloom filters are equal.
get_property/2
is_element/2	returns true if the bloom filter contains item.
item_count/1	Gets the number of items inserted into this bloom filter.
join/2	joins two bloom filter, returned bloom filter represents their union.
new_bin/3	Creates a new bloom filter with the given binary, hash function set and item count.
new_bpi/3	Creates a new bloom filter with the given hash function set and a fixed number of bits per item.
new_fpr/2	Creates a new bloom filter with the default (optimal) hash function set based on the given false positive rate.
new_fpr/3	Creates a new bloom filter with the given hash function set based on the given false positive rate.
p_add_list_v1/4
p_add_list_v2/4
print/1	Return bloom filter debug information.
resize/2	Increases Val until Val rem Div == 0.

Function Details

new_fpr/2

new_fpr(MaxItems :: non_neg_integer(), FPR :: float()) ->
           bloom_filter()

Creates a new bloom filter with the default (optimal) hash function set based on the given false positive rate.

new_fpr/3

new_fpr(MaxItems :: non_neg_integer(),
        FPR :: float(),
        Hfs :: hfs_lhsp:hfs()) ->
           bloom_filter()

Creates a new bloom filter with the given hash function set based on the given false positive rate.

new_bpi/3

new_bpi(MaxItems :: non_neg_integer(),
        BitsPerItem :: float(),
        Hfs :: hfs_lhsp:hfs()) ->
           bloom_filter()

Creates a new bloom filter with the given hash function set and a fixed number of bits per item.

new_bin/3

new_bin(Filter :: binary(),
        Hfs :: hfs_lhsp:hfs(),
        ItemsCount :: non_neg_integer()) ->
           bloom_filter()

Creates a new bloom filter with the given binary, hash function set and item count.

p_add_list_v1/4

p_add_list_v1(Hfs :: hfs_lhsp:hfs(),
              BFSize :: non_neg_integer(),
              BF1 :: binary(),
              Items :: [key()]) ->
                 BF2 :: binary()

p_add_list_v2/4

p_add_list_v2(Hfs :: hfs_lhsp:hfs(),
              BFSize :: non_neg_integer(),
              BF1 :: binary(),
              Items :: [key()]) ->
                 BF2 :: binary()

is_element/2

is_element(Bloom :: bloom_filter(), Item :: key()) -> boolean()

returns true if the bloom filter contains item

item_count/1

item_count(Bloom :: bloom_filter()) -> non_neg_integer()

Gets the number of items inserted into this bloom filter.

join/2

join(Bloom :: bloom_filter(), X2 :: bloom_filter()) ->
        bloom_filter()

joins two bloom filter, returned bloom filter represents their union

equals/2

equals(Bloom :: bloom_filter(), X2 :: bloom_filter()) -> boolean()

Checks whether two bloom filters are equal.

get_property/2

get_property(Bloom :: bloom_filter(), X2 :: fpr) -> float()

calc_HF_numEx/2

calc_HF_numEx(N :: non_neg_integer(), FP :: float()) ->
                 pos_integer()

Calculates the optimal number of hash functions for a bloom filter with N elements and a false positive probability FP.

calc_HF_num/2

calc_HF_num(M :: pos_integer(), N :: non_neg_integer()) ->
               K :: pos_integer()

Calculates optimal number of hash functions for an M-bit large BloomFilter with a maximum of N Elements.

calc_least_size_opt/2

calc_least_size_opt(N :: non_neg_integer(), FP :: float()) ->
                       M :: pos_integer()

Calculates the number of bits needed by a bloom filter to have a false positive probability of FP using up to N elements and the optimal number of hash functions K = ln(2)*M/N. M = N * log_2(1/FP) / ln(2) = - N * log_2(FP) / ln(2)

calc_least_size/3

calc_least_size(N :: non_neg_integer(),
                FP :: float(),
                K :: pos_integer()) ->
                   M :: pos_integer()

Calculates the number of bits needed by a bloom filter to have a false positive probability of FP using K hash functions and up to N-Elements. M = 1/(1-(1-(FP)^(1/K))^(1/(KN)))

calc_FPR/3

calc_FPR(M :: pos_integer(),
         N :: non_neg_integer(),
         K :: pos_integer()) ->
            FP :: float()

Calculates FP for an M-bit large bloom filter with K hash funtions and a maximum number of N elements. FP = (1-(1-1/M)^(K*N))^K

resize/2

resize(Val :: non_neg_integer(), Div :: pos_integer()) ->
          NewVal :: non_neg_integer()

Increases Val until Val rem Div == 0.

Generated by EDoc, Jul 23 2015, 22:20:30.