package bloomf

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Generic interface
1. Serializers/Deserializers
Functorial interface

package bloomf

bloomf
- Bloomf
  - Hashable
  - Make
    
    H

Legend:
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.

Generic interface

type 'a t

The type of the Bloom filter.

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.

raises Invalid_argument
if error_rate is not in ]0, 1[, or size is negative.

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.

val union : 'a t -> 'a t -> 'a 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

val inter : 'a t -> 'a t -> 'a t

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).

Serializers/Deserializers

val to_bytes : 'a t -> bytes

val of_bytes : bytes -> ('a t, [ `Msg of string ]) result

Functorial interface

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

module type Hashable = sig ... end

The input interface for Bloomf.Make.

module Make (H : Hashable) : sig ... end

The output interface for Bloomf.Make.