package grenier

  1. Overview
  2. Docs
On This Page
  1. Serialization
A collection of various algorithms in OCaml

Install 

dune-project
 Dependency

github.com Readme Changelog Edit opam file Versions (11)

Authors

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Maintainers

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Sources

grenier-v0.10.tbz
sha256=271ae9461d012c99449e5233386b13ab99ae2e474ed570e05bf0c9947e5eff1e
sha512=73c89aa6281f612c499eb734c6fc4d33b961ed82d6cc7380b03acb196233c27107e103b11f55e50f543f0f1dedb4924e6691a5c3c353ef4d8177bc661fc2bfd4

doc/grenier.hll/Hll/index.html

Module Hll

An implementation of HyperLogLog probabilistic cardinality estimator.

type t

Type of HyperLogLog counters

val make : error:float -> t

Create a new counter with error error rate. error should verify 0.0 < error && error < 1.0. 0.05 is a reasonable default.

Use estimate_memory to measure memory consumption and runtime of this function.

val add : t -> int64 -> unit

add t k counts item k in t.

k should be "random": it should be the output of some cryptographic hashing algorithm like SHA. It is not treated as an integer. This is key to getting proper results. No patterns should appear in the bits of the different items added.

Runtime is O(1).

val estimate_memory : error:float -> int

Estimate the memory consumed in bytes by a counter with the specified error rate.

This ignores the constant overhead of the OCaml representation, around two words. It is a bytes of estimate_memory ~error + 1 length.

val card : t -> float

Get the cardinality estimation. Defaults to HyperLogLog++.

val card_hll : t -> float
val card_hllpp : t -> float
val copy : t -> t

Get a copy of a counter.

val merge : into:t -> t -> unit

merge ~into:t0 t' has the same effect as adding all items added to t' to t0.

t0 and t' must have been constructed with the same error rate!

val clear : t -> unit

Reset counter to 0.

val hash_int64 : int64 -> int64

The following algorithm provide a reasonable hashing function for integers, if you want to feed the HLL with "normal" integers.

Serialization

val to_string : t -> string

Returns a string with the current state stored.

val of_string : string -> t

Restore a HLL saved with to_string.

of_string (to_string t) is functionnally equivalent to copy t, except a bit more expensive.

It can raise Invalid_argument if the string provided was not saved by to_string.