3 ms·
One 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
by bulldoa 8y ago
One 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.