hyperloglog

HyperLogLog Distinct Value Estimator
====================================

HyperLogLog (HLL) is a probabilistic
estimator of the cardinality of a stream of values. Given
a bounded amount of memory, it can estimate the cardinality of a stream with bounded relative error
and it is possible to trade off memory usage for precision. Formally, the standard error for an HLL
with n registers is less than 1.04/sqrt(n).

Example
-------

``javascript
var HyperLogLog = require('hyperloglog');
var hll = HyperLogLog(12);

// Insert three values, two of them distinct.
hll.add(HyperLogLog.hash("value1"));
hll.add(HyperLogLog.hash("value2"));
hll.add(HyperLogLog.hash("value1"));

assert(2 === hll.count());
`

API
---

$3

In order to count items, they must first be hashed. The hash() function provides a suitable hash.
Its output is an array of four 32 bit postive integers, which, taken together constitute the complete
hash of the input string. Currently the implementation is MurmurHash3-128.

$3

Construct an HLL data structure with n bit indices into the register array. This implies that
there will be 2^n registers. Typical values for n are around 12, which would use 4096 registers and
yield less than 1.625% relative error. Higher values use more memory, but provide greater precision.

$3

Adds a hash to the HLL. The hash must be in the format emitted by hash(). If

$3

Get the current estimate of the number of distinct values that have been added.

$3

Get the expected relative error, based on the number of registers. This will not change as
values are added. The absolute standard error is the relative error multiplied by the estimated
cardinality from count().

$3

Return an external representation of the internal HLL state. This may be useful for serializing,
storing, and migrating an HLL. The format returned is the same as that accepted by merge().

$3

Merge another HLL's state into this HLL. The data must be of the same form as that returned by output().
If the incoming data has fewer registers than this HLL, this one will be folded down to be the same size as the
incoming data, with a corresponding loss of precision. If the incoming data has more registers, it will be folded
down as it is merged. The result is that this HLL will be updated as though it had processed all values that were
previously processed by either HLL.

`javascript
hll1.add(hash1);
hll1.add(hash2);

hll2.add(hash2);
hll2.add(hash3);

hll1.merge(hll2.output());

assert(3 === hll1.count());
``

Possible Improvements
---------------------

- Make HLL use a compressed representation from Google's paper
- Bit shift registers to use 6 bits per register instead of 8 since we only ever actually use 6 for up to 2^64 (2^2^6).
- Go to 5 bits per register and add the high cardinality correction. Save 16% on storage for effectively the same standard error.