database - ¿Cómo funciona el algoritmo HyperLogLog?

algorithm math

Question

He estado aprendiendo acerca de diferentes algoritmos en mi tiempo libre recientemente, y uno que encontré que parece ser muy interesante se llama algoritmo HyperLogLog, que calcula cuántos elementos únicos hay en una lista.

Esto fue particularmente interesante para mí porque me devolvió a mis días de MySQL cuando vi ese valor de "cardinalidad" (que siempre asumí hasta hace poco que no se calculó).

Entonces sé cómo escribir un algoritmo en O ( n ) que calculará cuántos elementos únicos hay en una matriz. Escribí esto en JavaScript:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

Pero el problema es que mi algoritmo, mientras que O ( n ), usa mucha memoria (almacenando valores en la Table ).

He estado leyendo este artículo sobre cómo contar duplicados en una lista en el tiempo O ( n ) y usando memoria mínima.

Explica que al mezclar y contar bits o algo se puede estimar dentro de una cierta probabilidad (suponiendo que la lista esté distribuida uniformemente) el número de elementos únicos en una lista.

He leído el documento, pero parece que no puedo entenderlo. ¿Alguien puede dar una explicación más profano? Sé lo que son los hashes, pero no entiendo cómo se usan en este algoritmo HyperLogLog.

Answer 1

El truco principal detrás de este algoritmo es que si usted, al observar una secuencia de números enteros aleatorios, ve un número entero cuya representación binaria comienza con algún prefijo conocido, hay una mayor probabilidad de que la cardinalidad de la secuencia sea 2 ^ (tamaño del prefijo) .

Es decir, en una secuencia aleatoria de enteros, ~ 50% de los números (en binario) comienza con "1", 25% comienza con "01", 12,5% comienza con "001". Esto significa que si observa una secuencia aleatoria y ve un "001", hay una mayor probabilidad de que esta secuencia tenga una cardinalidad de 8.

(El prefijo "00..1" no tiene ningún significado especial. Está ahí simplemente porque es fácil encontrar el bit más significativo en un número binario en la mayoría de los procesadores)

Por supuesto, si observa un solo entero, la posibilidad de que este valor sea incorrecto es alto. Es por eso que el algoritmo divide la secuencia en substreams independientes "m" y mantiene la longitud máxima de un prefijo "00 ... 1" de cada substream. Luego, estima el valor final tomando el valor medio de cada flujo secundario.

Esa es la idea principal de este algoritmo. Hay algunos detalles faltantes (la corrección para valores estimados bajos, por ejemplo), pero está bien escrito en el documento. Perdón por el terrible inglés.

Answer 2

La intuición es que si su entrada es un gran conjunto de números aleatorios (por ejemplo, valores hash), deben distribuirse uniformemente en un rango. Digamos que el rango es de hasta 10 bits para representar el valor hasta 1024. Luego se observó el valor mínimo. Digamos que es 10. Entonces la cardinalidad se estimará en alrededor de 100 (10 × 100 ≈ 1024).

Lea el documento para conocer la lógica real, por supuesto.

Otra buena explicación con código de ejemplo se puede encontrar aquí:
Damn Cool Algorithms: Estimación de cardinalidad - Nick''s Blog

Answer 3

Un HyperLogLog es una estructura de datos probabilísticos . Cuenta la cantidad de elementos distintos en una lista. Pero en comparación con una forma directa de hacerlo (tener un conjunto y agregar elementos al conjunto) lo hace de una manera aproximada.

Antes de ver cómo lo hace el algoritmo HyperLogLog, uno tiene que entender por qué lo necesita. El problema con una forma directa es que consume O(distinct elements) del espacio. ¿Por qué hay una gran notación O aquí en lugar de solo elementos distintos? Esto se debe a que los elementos pueden ser de diferentes tamaños. Un elemento puede ser 1 otro elemento "is this big string" . Entonces, si tienes una gran lista (o una gran cantidad de elementos), se necesitará mucha memoria.

Conteo probabilístico

¿Cómo se puede obtener una estimación razonable de una serie de elementos únicos? Suponga que tiene una cadena de longitud m que consiste en {0, 1} con la misma probabilidad. ¿Cuál es la probabilidad de que comience con 0, con 2 ceros, con k ceros? Es 1/2 , 1/4 y 1/2 1/2^k . Esto significa que si ha encontrado una cadena con k ceros, ha observado aproximadamente 2^k elementos. Este es un buen punto de partida. Teniendo una lista de elementos que están distribuidos uniformemente entre 0 y 2^k - 1 , puedes contar el número máximo del prefijo mayor de ceros en la representación binaria y esto te dará una estimación razonable.

El problema es que la suposición de tener números distribuidos uniformemente desde 0 t 2^k-1 es demasiado difícil de lograr (los datos que encontramos no son números, casi nunca distribuidos uniformemente, y pueden estar entre cualquier valor. La función hash puede suponer que los bits de salida se distribuirán uniformemente y la mayoría de las funciones hash tienen salidas entre 0 y 2^k - 1 ( SHA1 da valores entre 0 y 2^160 ). Entonces, lo que hemos logrado hasta ahora es que puede estimar el número de elementos únicos con la cardinalidad máxima de k bits almacenando solo un número de bits log(k) de tamaño. La desventaja es que tenemos una gran variación en nuestra estimación. Una cosa genial que casi creamos el conteo probabilístico de 1984 papel (es un poco más inteligente con la estimación, pero aún estamos cerca).

LogLog

Antes de avanzar, tenemos que entender por qué nuestra primera estimación no es tan buena. La razón detrás de esto es que una ocurrencia aleatoria de elemento de prefijo 0 de alta frecuencia puede echar a perder todo. Una forma de mejorarlo es usar muchas funciones hash, contar máximo para cada una de las funciones hash y al final promediarlas. Esta es una idea excelente, que mejorará la estimación, pero el documento LogLog utilizó un enfoque ligeramente diferente (probablemente porque el hashing es bastante caro).

Usaron un hash pero lo dividieron en dos partes. Uno se llama cubo (el número total de cubos es 2^x ) y el otro es básicamente el mismo que nuestro hash. Fue difícil para mí entender lo que estaba pasando, así que daré un ejemplo. Supongamos que tiene dos elementos y su función hash que da valores de 0 a 2^10 produce 2 valores: 344 y 387 . Decidiste tener 16 cubos. Así que tienes:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

Al tener más cubos, disminuyes la varianza (utilizas un poco más de espacio, pero aún es muy pequeño). Usando habilidades matemáticas, pudieron cuantificar el error (que es 1.3/sqrt(number of buckets) ).

HyperLogLog

HyperLogLog no introduce ninguna idea nueva, pero utiliza principalmente muchas matemáticas para mejorar la estimación anterior. Los investigadores han descubierto que si elimina el 30% de los números más grandes de los segmentos, mejora significativamente la estimación. También usaron otro algoritmo para promediar números. El documento es matemático pesado.

Y quiero terminar con un artículo reciente, que muestra una versión mejorada del algoritmo hyperLogLog (hasta ahora no tuve tiempo para entenderlo completamente, pero quizás más adelante mejore esta respuesta).