HyperLogLog and HyperLogLog++
Implements the HyperLogLog and HyperLogLog++ algorithms.
HyperLogLog paper: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
HyperLogLog++ paper: http://research.google.com/pubs/pub40671.html
Documentation can be found here.
Comparison of Algorithms
The HyperLogLog++ algorithm has much lower error for small cardinalities. This is because it uses a different representation of data for small sets of data. Data generated using this library shows the difference for N < 10000:
HyperLogLog++ also has bias correction which helps offset estimation errors in the original HyperLogLog algorithm. This correction can be seen here, again using data generated using this library:
- Right now HLL++ uses 8 bits per register. It could use 6 bits and take less memory.
- The list compression algorithm could be improved, allowing the sparse representation to be used longer.