algorithm - para - Explicando el algoritmo de croquis de cuenta

algoritmo de bresenham para circunferencias c++

Question

¿Alguien puede explicar cómo funciona el algoritmo de conteo de bocetos? Todavía no puedo entender cómo se utilizan los hashes, por ejemplo. Me cuesta entender este artículo .

Answer 1

Count sketch es una estructura de datos probabilística que le permite responder la siguiente pregunta:

Leyendo un flujo de elementos a1, a2, a3, ..., an donde puede haber muchos elementos repetidos, en cualquier momento le dará la respuesta a la siguiente pregunta: cuántos elementos ai ha visto hasta ahora.

Claramente, puede obtener un valor exacto en cada momento simplemente manteniendo el hash donde las claves son su ai y los valores es cuántos elementos ha visto hasta ahora. Es rápido O(1) agrega, O(1) marca y te da un recuento exacto. El único problema que ocupa el espacio O(n) , donde n es el número de elementos distintos (tenga en cuenta que el tamaño de cada elemento tiene una gran diferencia porque se necesita way more space to store this big string as a key que solo this

Entonces, ¿cómo te va a ayudar el boceto del Conde? Como en todas las estructuras de datos probabilísticas, sacrificas la certeza por el espacio. El boceto de conteo le permite seleccionar 2 parámetros: precisión de los resultados ε y probabilidad de mala estimación δ.

Para hacer esto, seleccionas una familia de funciones hash independientes por pares . Estas palabras complicadas significan que no chocan con frecuencia (de hecho, si ambos valores de hash mapean en el espacio [0, m] la probabilidad de colisión es aproximadamente 1/m^2 ). Cada una de estas funciones hash asigna los valores a un espacio [0, w] . Así que creas una matriz d * w .

Ahora para cuando lea el elemento, calcule cada uno de los hashes d de este elemento y actualice los valores correspondientes en el boceto. Esta parte es la misma para el croquis Count y el croquis Count-min.

Insomniac explicó muy bien la idea (calculando el valor esperado) para el boceto de conteo, así que solo diré que con count-min todo es incluso más simple. Solo calcule d hashes del valor que desea obtener y devuelva el más pequeño de ellos. Sorprendentemente, esto proporciona una gran garantía de precisión y probabilidad, que puede encontrar aquí .

Al aumentar el rango de funciones hash, aumentar la precisión de los resultados, aumentar el número de hashes disminuye la probabilidad de una mala estimación: ε = e / w y δ = 1 / e ^ d. Otra cosa interesante es que el valor siempre se sobreestima (si lo encontró, probablemente sea más grande que el valor real, pero seguramente no menor).

Answer 2

Este algoritmo de transmisión crea una instancia del siguiente marco.

1. Encuentre un algoritmo de transmisión aleatorio cuya salida (como variable aleatoria) tenga la expectativa deseada pero generalmente una varianza alta (es decir, ruido).

2. Para reducir la varianza / ruido, ejecute muchas copias independientes en paralelo y combine sus salidas.

Por lo general, 1 es más interesante que 2. En realidad, el 2 de este algoritmo es un tanto no estándar, pero solo hablaré de 1.

Supongamos que estamos procesando la entrada

a b c a b a .

Con tres contadores, no hay necesidad de hash.

a: 3, b: 2, c: 1

Supongamos, sin embargo, que sólo tenemos uno. Hay ocho funciones posibles h : {a, b, c} -> {+1, -1} . Aquí hay una tabla de los resultados.

 h  |
abc |  X = counter
----+--------------
+++ | +3 +2 +1 =  6
++- | +3 +2 -1 =  4
+-- | +3 -2 -1 =  0
+-+ | +3 -2 +1 =  2
--+ | -3 -2 +1 = -4
--- | -3 -2 -1 = -6
-+- | -3 +2 -1 = -2
-++ | -3 +2 +1 =  0

Ahora podemos calcular las expectativas.

            (6 + 4 + 0 + 2) - (-4 + -6 + -2 + 0)
E[h(a) X] = ------------------------------------ = 24/8 = 3
                             8

            (6 + 4 + -2 + 0) - (0 + 2 + -4 + -6)
E[h(b) X] = ------------------------------------ = 16/8 = 2
                             8

            (6 + 2 + -4 + 0) - (4 + 0 + -6 + -2)
E[h(c) X] = ------------------------------------ =  8/8 = 1 .
                             8

¿Que está pasando aqui? Para a , digamos, podemos descomponer X = Y + Z , donde Y es el cambio en la suma para a s, y Z es la suma para no s. Por la linealidad de la expectativa, tenemos

E[h(a) X] = E[h(a) Y] + E[h(a) Z] .

E[h(a) Y] es una suma con un término para cada aparición de a que es h(a)^2 = 1 , por lo que E[h(a) Y] es el número de apariciones de a . El otro término E[h(a) Z] es cero; incluso dado a h(a) , es probable que cada uno de los otros valores hash sea más o menos uno y, por lo tanto, contribuya con cero en la expectativa.

De hecho, la función hash no necesita ser aleatoria uniforme, y algo bueno: no habría manera de almacenarla. Basta con que la función hash sea independiente por pares (cualquiera de los dos valores hash particulares son independientes). Para nuestro ejemplo simple, una selección aleatoria de las siguientes cuatro funciones es suficiente.

abc

+++
+--
-+-
--+

Te dejaré los nuevos cálculos.