HyperLogLog
HyperLogLog aproxima la cardinalidad (conteo de distintos) a partir de los ceros iniciales de los valores hash, estimando conteos distintos enormes en una memoria fija pequeña.
Propósito
Contar aproximadamente miles de millones de elementos distintos en memoria fija (~KB), usado para estadísticas de visitantes únicos.
Mecanismo
Se aplica hash a cada elemento, se agrupa por los primeros k bits y se registra en cada cubo el máximo número de ceros iniciales de los bits restantes. La estimación de cardinalidad ≈ α·m²·∑2^M[i]. El error relativo es de aproximadamente 1.04/√m. Redis PFCOUNT lo usa.
Casos de uso
- Estadísticas de visitantes únicos
- Estimación de cardinalidad
- Conteo distinto en streams