Module cbf

Counting Bloom Filter implementation.

Copyright © 2016 Zuse Institute Berlin

Version: $Id$

Authors: Nico Kruber (kruber@zib.de), Maik Lange (malange@informatik.hu-berlin.de).

References

Description

Counting Bloom Filter implementation

Data Types

cbf()

abstract datatype: cbf()

key()

key() = any()

Function Index

new_fpr/2Creates a new counting bloom filter with the default (optimal) hash function set based on the given false positive rate.
new_fpr/3Creates a new counting bloom filter with the given hash function set based on the given false positive rate.
new_bpi/3Creates a new counting bloom filter with the given hash function set and a fixed number of positions (bits in standard bloom filters) per item.
new_bin/3Creates a new counting bloom filter with the given binary, hash function set and item count.
new/2Creates a new counting bloom filter.
add/2Adds one item to the counting bloom filter.
add_list/2Adds multiple items to the counting bloom filter.
p_add_list/4Helper to add items to the counting bloom filter.
remove/2Removes one item from the counting bloom filter.
remove_list/2Removes multiple items from the counting bloom filter.
is_element/2Returns true if the counting bloom filter contains this item.
item_count/1Gets the number of items inserted into this counting bloom filter.
join/2Joins two counting bloom filters so that the returned counting bloom filter represents their union.
minus/2Subtracts counting bloom filter A from B so that the returned counting bloom filter that approximates the set difference (with false positives and false negatives!).
to_bloom/1
equals/2Checks whether two counting bloom filters are equal.
print/1Returns counting bloom filter debug information.
get_property/2

Function Details

new_fpr/2

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

Creates a new counting 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_plain:hfs() | non_neg_integer()) ->
           cbf()

Creates a new counting 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 :: number(),
        Hfs :: hfs_plain:hfs() | non_neg_integer()) ->
           cbf()

Creates a new counting bloom filter with the given hash function set and a fixed number of positions (bits in standard bloom filters) per item.

new_bin/3

new_bin(Filter :: array:array(integer()),
        HfCount :: hfs_plain:hfs() | non_neg_integer(),
        ItemsCount :: non_neg_integer()) ->
           cbf()

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

new/2

new(BitSize :: pos_integer(),
    HfCount :: hfs_plain:hfs() | non_neg_integer()) ->
       cbf()

Creates a new counting bloom filter.

add/2

add(Cbf :: cbf(), Item :: key()) -> cbf()

Adds one item to the counting bloom filter.

add_list/2

add_list(Cbf :: cbf(), Items :: [key()]) -> cbf()

Adds multiple items to the counting bloom filter.

p_add_list/4

p_add_list(Hfs :: hfs_plain:hfs(),
           BFSize :: pos_integer(),
           BF1 :: array:array(integer()),
           Items :: [key()]) ->
              BF2 :: array:array(integer())

Helper to add items to the counting bloom filter.

remove/2

remove(Cbf :: cbf(), Item :: key()) -> cbf()

Removes one item from the counting bloom filter. (may introduce false negatives if removing an item not added previously)

remove_list/2

remove_list(Cbf :: cbf(), Items :: [key()]) -> cbf()

Removes multiple items from the counting bloom filter. (may introduce false negatives if removing an item not added previously)

is_element/2

is_element(Cbf :: cbf(), Item :: key()) -> boolean()

Returns true if the counting bloom filter contains this item.

item_count/1

item_count(Cbf :: cbf()) -> non_neg_integer()

Gets the number of items inserted into this counting bloom filter.

join/2

join(Cbf :: cbf(), BF2 :: cbf()) -> cbf()

Joins two counting bloom filters so that the returned counting bloom filter represents their union.

minus/2

minus(A :: cbf(), B :: cbf()) -> cbf()

Subtracts counting bloom filter A from B so that the returned counting bloom filter that approximates the set difference (with false positives and false negatives!).

to_bloom/1

to_bloom(Cbf :: cbf()) -> bloom:bloom_filter()

equals/2

equals(Cbf :: cbf(), X2 :: cbf()) -> boolean()

Checks whether two counting bloom filters are equal.

print/1

print(Cbf :: cbf()) -> [{atom(), any()}]

Returns counting bloom filter debug information.

get_property/2

get_property(Cbf :: cbf(), X2 :: fpr) -> float()


Generated by EDoc, Aug 2 2016, 13:43:20.