3 ms·
Original HLL paper from 2007: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
by massaman_yams 8y ago
Original HLL paper from 2007:
http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
- bulldoa 8y agoOne of the key quality that hyperloglog relies on is that the action of hash distributes any input to any output with equal probability (eg. any input have 1/m chance to be in a particular point in output space where m is the cardinality of the output space) I can't seem to prove this rigorously, am I understanding the paper correclty?
- massaman_yams 8y agoI think it's more a practical concern than something that can be proven conclusively; the behavior characteristics (e.g., collision probability) are known for a given hash function, and if you're implementing HLL, you choose an appropriate one based on your use case (expected cardinality, etc.) Redis uses a modified 64-bit MurmurHash2, for example.