El contador LogLog y su sucesor, HyperLogLog Flajolet et al. 2008 son estructuras de datos probabilísticas que tienen como objetivo contar los elementos distintos de un conjunto dentro de [math] \ epsilon [/ math] del valor verdadero, con alguna probabilidad [math] \ geq 1- \ delta [/ math].
Realmente recomiendo leer el documento, pero la configuración del problema es la siguiente. Digamos que extrae sus datos de un dominio finito
[matemáticas] \ {1, 2, \ ldots, n \} [/ matemáticas]
y digamos que seleccionamos algunos elementos de este conjunto [math] x_1, x_2, \ ldots x_N [/ math] y deseamos saber [math] D [/ math], cuántos elementos distintos tenemos.
Puede asignar aleatoriamente (con una función hash aleatoria, por ejemplo) sus elementos de conjunto para que aparezcan como variables aleatorias uniformes, dentro de algún rango [matemático] [0, m] [/ matemático], luego cada uno de los bits de sus elementos asignados aleatoriamente se distribuirá aproximadamente Bernoulli (1/2).
- ¿Cuáles son algunos programas / algoritmos recursivos interesantes (como la Torre de Hanoi y N-Queens)?
- ¿Quién sabe qué hay detrás de la API de Google Nearby Search? ¿Qué algoritmo usan? ¿Cómo encuentra Google una estación de servicio cercana?
- ¿Cuál es la forma más fácil de demostrar que si la intersección de 2 rutas es un gráfico conectado, entonces la unión de las 2 rutas tiene al menos un circuito?
- ¿Por qué es 5n + 8n ^ 2 + 100n ^ 3 = O (n ^ 4)?
- ¿Qué harías? ¿Cuál hubiera sido tu estrategia si hubieras tenido la oportunidad de volver a comenzar la programación de aprendizaje?
A partir de esta observación, podemos ver que el número de ceros finales en los bits de cada elemento asignado aleatoriamente se distribuirá aproximadamente Geométrico (1/2). Podemos almacenar el número máximo de ceros finales, M, de los bits de todos nuestros elementos mapeados, lo que requiere espacio [math] \ mathcal {O} (\ log \ log n) [/ math], de ahí el nombre. M se usará para estimar [matemáticas] D [/ matemáticas].
¿Cómo? Bueno, M se distribuirá estrechamente alrededor de [math] \ mathbb {E} (M) [/ math], que es igual a la expectativa del máximo de [math] D [/ math] geométrico truncado (1/2) al azar variables: una cantidad que se puede calcular (no tiene una expresión de forma bastante cerrada) que podemos llamar [matemáticas] f (D) [/ matemáticas]. Así
[matemáticas] f ^ {- 1} (M) [/ matemáticas]
es nuestra estimación de [matemáticas] D [/ matemáticas]. Solo se basa en M y, como se indicó, esto solo requiere espacio de registro.
Entonces, si tu dominio es realmente enorme, por ejemplo, n = [math] 2 ^ {384} [/ math] para triples de direcciones ipv6, entonces un cálculo de cardinalidad exacto que requiere [math] \ mathcal {\ theta} (n) [/ math] espacio ya no es posible pero LogLog Puede proporcionar buenas estimaciones.
