Library

Module

Module type

Parameter

Class

Class type

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">

On This Page

Legend:

Library

Module

Module type

Parameter

Class

Class type

Library

Module

Module type

Parameter

Class

Class type

Bloom filters

bloomf is an implementation of Bloom filters in OCaml.

Bloom filters are memory and time efficient data structures allowing probabilistic membership queries in a set. A query negative result ensures that the element is not present in the set, while a positive result might be a false positive, i.e. the element might not be present and the BF membership query can return true anyway. Internal parameters of the BF allow to control its false positive rate depending on the expected number of elements in it.

`val create : ?error_rate:float -> int -> 'a t`

`create ~error_rate size`

creates a fresh BF for which expected false positive rate when filled with `size`

elements is `error_rate`

.

`val add : 'a t -> 'a -> unit`

`add t e`

adds `e`

to `t`

.

`val mem : 'a t -> 'a -> bool`

`mem t e`

is `true`

if `e`

is in `t`

.

`val clear : 'a t -> unit`

`clear t`

clears the contents of `t`

.

`union t1 t2`

computes the union of the two inputs. This operation is lossless in the sense that the resulting Bloom filter is the same as the Bloom filter created from scratch using the union of the two sets.

Raises `Invalid_argument`

if the two bloom filters were created with different parameters

`inter t1 t2`

computes the intersection of the two inputs. The false positive probability in the resulting Bloom filter is at most the false-positive probability in one of the constituent Bloom filters, but may be larger than the false positive probability in the Bloom filter created from scratch using the intersection of the two sets.

Raises `Invalid_argument`

if the two bloom filters were created with different parameters

`val size_estimate : 'a t -> int`

`size_estimate t`

is an approximation of the number of elements stored in the bloom filter. Please note that this operation is costly (see benchmarks).

`val to_bytes : 'a t -> bytes`

The functorial interface allows you to specify your own hash function.

`module type Hashable = sig ... end`

The input interface for `Bloomf.Make`

.

On This Page