3 ms·

This article is old but really good at explaining HyperLogLog: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation http://blog.notdot.net/

• wallacoloo 5y ago
  > Specifically, by throwing out the 30% of buckets with the largest values, and averaging only 70% of buckets with the smaller values, accuracy can be improved from 1.30/sqrt(m) to only 1.05/sqrt(m)! How do you do this without sorting? Or, do you approximate again by throwing out everything < 0.3 * max_hash? It’s not obvious to me how that approach would actually give any better results: the spacing between 0.3 * max_hash and the next lowest hash is just as prone to variance as the distance between 0 and the absolute lowest hash, and it’s that distance which feeds the estimate.