joegreen0991/hyperloglog

A hyper log log with min hash data structure library, for counting cardinalities. Union and intersection capable

v1.0.0 2014-07-10 09:55 UTC

Requires

• php: >=5.3.0

MIT

• Joe Green

• unique
• hyperloglog
• hyper log log
• min hash
• cardinalities
• cardinality

README

PHP implementation of the HyperLogLog algorithm. Based on Antirez/Redis implementation.

Resources

• The original HLL algorithm from Phillipe Flajolet
• An actual paper on the algorithm with real maths and scary equations.
• Awesome explanation and experimental data from AdRoll
• Very nice blog post explaining what the HLL this is ;)

Note!

This version has been tuned to work with a P value of 14. This is a register size of 2^14 Bytes = 16KB

There is a large bias that can be seen in the graphs below, which begins when the set cardinality reaches around 2^P * 2.5. Polynomial regression has been used to calculate bias offsets BUT ONLY FOR P = 14. You are free to change the P value but the bias offsets will not be applied. Check out the code for more information

Some Professional Looking Graphs

####HyperLogLog

P=14

P=16 Note the offset bias around 2.5 * 2^16 ~= 165,000

P=20 Note the offset bias around 2.5 * 2^20 ~= 2,600,000

####MinHash

K=8192