Type of HyperLogLog counters

Create a new counter with error error rate (the relative standard error of the estimation). error should verify 0.0 < error && error < 1.0. 0.05 is a reasonable default.

The number of registers is a power of two between 2^4 and 2^18, so the error is at most 26% and at least 0.2%, whatever error asks.

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

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

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.

Get the cardinality estimation. Defaults to HyperLogLog++.

Get a copy of a counter.

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!

Reset counter to 0.

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

Returns a string with the current state stored.

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.