El Conde Boceto Algoritmo

Question

Puede alguien explicar cómo el conde Boceto algoritmo funciona? Todavía no puedo entender cómo se usan los hash, por ejemplo. Me cuesta entender this paper.

Answer 1

Este algoritmo de streaming instancia el siguiente marco.

1. Encuentra un algoritmo aleatorio de streaming cuya salida (como una variable aleatoria) tiene la expectativa deseada pero generalmente alta varianza (es decir, el ruido).

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

Por lo general 1 es más interesante que la de 2 2. Este algoritmo realidad es algo no estándar, pero voy a hablar de 1 solamente.

Supongamos que estamos procesar 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 tenemos solo una. 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 

Qué pasa aquí? Para a, digamos que podemos descomponer X = Y + Z, donde Y es el cambio en la suma para a s, y Z es la suma para los valores no a s. Por la linealidad de las expectativas, tenemos

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

E[h(a) Y] es una suma de un término para cada ocurrencia de a que es h(a)^2 = 1, por lo E[h(a) Y] es el número de ocurrencias de a. El otro término E[h(a) Z] es cero; incluso dado h(a), el otro valor hash es igualmente probable que sea más o menos uno y así contribuye cero en la expectativa.

De hecho, la función hash no necesita ser uniforme al azar, y una buena cosa: no habría manera de almacenarlo. Es suficiente que la función hash sea independiente de pares (cualquier dos valores hash particulares son independientes). Para nuestro ejemplo simple, una elección aleatoria de las siguientes cuatro funciones es suficiente.

abc 

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

Voy a dejar los nuevos cálculos para usted.

Answer 2

boceto Count es un probabilistic data structure que le permite responder a la siguiente pregunta: ¿

lectura una corriente de elementos a1, a2, a3, ..., an donde puede haber una gran cantidad de elementos repetidos, en cualquier momento que le dará la respuesta a la siguiente pregunta: cuántos elementos ai has visto hasta ahora.

---

Puede obtener claramente un valor exacto en cada momento con sólo mantener el hash donde las claves son sus ai y valores es el número de elementos que han visto hasta ahora. Es rápido O(1) agregar, O(1) verificar y le da un recuento exacto. El único problema que se necesita O(n) espacio, donde n es el número de elementos distintos (tener en cuenta que el tamaño de cada elemento tiene una gran diferencia, ya que toma way more space to store this big string as a key que sólo this.

---

Entonces, ¿cómo Count boceto Como en todas las estructuras de datos probabilísticas sacrifica certeza por el espacio. Contar boceto le permite seleccionar 2 parámetros: precisión de los resultados y épsilon y probabilidad de mala estimación δ.

Para ello, seleccione un familia de dpairwise independent hash functions. Estas palabras complicadas significan que n ot colisiona a menudo (de hecho, si ambos hashes asignan valores al espacio [0, m], la probabilidad de colisión es de aproximadamente 1/m^2). Cada una de estas funciones hash asigna los valores a un espacio [0, w]. Entonces creas una matriz d * w.

Ahora, cuando lee el elemento, calcula cada uno de los valores hash d de este elemento y actualiza los valores correspondientes en el boceto. Esta parte es la misma para el boceto Count y el boceto Count-min.

Insomniac muy bien explicada la idea (el cálculo del valor esperado) para boceto recuento, así que sólo le dirá que con todo recuento-min es aún más simple. Simplemente calcula d hashes del valor que desea obtener y devuelve el más pequeño de ellos. Sorprendentemente, esto proporciona una gran garantía de precisión y probabilidad, que puede find here.

Aumentando el rango de funciones hash, aumenta la precisión de los resultados, aumentando el número de hashes disminuye la probabilidad de mala estimación: & epsilon; = e/w y δ = 1/e^d. Otra cosa interesante es que el valor siempre se sobrestima (si se encuentra el valor, probablemente sea más grande que el valor real, pero seguramente no más pequeño).