Hyperloglog and Cardinality Estimation

HyperLogLog is a probabilistic data structure used to estimate the cardinality (number of unique elements) of large data streams with minimal memory. Instead of storing all unique elements in a set, it uses hash functions and tracks the position of the rightmost set bit in hashed values. The probability distribution of rightmost set bits follows a pattern where the first unset bit position approximates 2^B unique elements. Redis implements this via PF commands (PFADD, PFCOUNT, PFMERGE), storing the filter in raw byte encoding. The Flajolet-Martin algorithm underpins this approach, using multiple hash functions and median averaging to reduce error, requiring only O(log M) space for M unique elements.