Streaming Flashcards
Reservoir sampling: para que sirve?
Entrega una meustra de tamano fijo del stream.
Reservoir sampling: algoritmo.
Para un stream infinito queremos guardar una muestra de tamaño constante “s”,si la cantidad de datos vistos hasta el momento es “n” entonces queremos que la probabilidad de que un dato esté en la muestra sea s/n.
Para los primeros “s” elementos todos se almacenan. Luego a partir del elemento s+1 se aplica una función de hashing 0..n y si el resultado es < s el dato se almacena y sino se descarta.
Momento de orden k de un stream.
sum (M_i)^k
M_i: frecuencia del elemento i-esimo.
Momento de orden 0. Que indica y como se calcula.
Cantidad de datos diferentes observados hasta el momento.
Se calcula con Flajolet Martin.
Momento de orden 1. Que indica y como se calcula.
Cant. de datos observados en el stream.
Se calcula con un simple contador.
Momento de orden 2. Que indica y como se calcula.
Es el Numero sorpresa. Es un indicador de si los datos en el stream se distribuyen en forma pareja o si algún dato aparece muchas mas veces que otro.
Se calcula con AMS.
Flajolet Martin: algoritmo.
Calcula la cantidad de elementos distintos observados hasta el momento en un stream
● A cada dato se le aplica una función de hashing que genera un número de m bits (m mayor a log2 n siendo n la cantidad de datos observados) y se observa con cuantos bits en cero comienza el resultado de la función.
● En memoria se mantiene la cantidad máxima de bits 0 observados que llamamos “r”.
● La cantidad de elementos diferentes en el stream puede estimarse como 2^r
Que problemas tiene Flajolet Martin? Como se soluciona?
● Un problema evidente del algoritmo es que es extremadamente sensible a resultados del hash que por ejemplo tengan muchos ceros a izquierda o peor aun que sean todos ceros.
● Para evitar esto se utilizan varias funciones de hashing y se llevan distintos contadores.
● Luego, dividiendo los contadores en grupos podemos tomar la media de cada grupo, evitando de esta forma la influencia de valores extremos y luego hacer un promedio de todas las medias.
HyperLogLog
- Usamos una única función de hashing de 64 bits (o más)
- Los primeros “n” bits nos dan el número de estimador.
- En los siguientes 64-n bits contamos la cantidad de ceros a izquierda.
- La estimación es el promedio armónico de los estimadores que usamos
AMS
● Se usa para calcular los momentos de orden 2, es decir el número sorpresa de un stream
● Se define un número “k” de variables a mantener en memoria. Cada variable k tiene 2 campos: valor y cantidad.
● Por cada elemento del stream si el elemento está en alguna de esas k variables entonces incrementar esa variable en 1.
● El momento de orden 2 se estima como el promedio de n(2c_i-1) donde n es la cantidad de datos vistos hasta el momento y c_i es la cantidad de cada variable k_i.
● Para mantener las “k” variables usaremos el algoritmo de reservoir sampling. (Cada vez que procesamos un dato del stream si el mismo está en la lista de variables aumentamos su frecuencia, si el dato no está entonces con probabilidad k/n reemplazamos al azar alguna de las variables por el dato nuevo inicializado en cantidad = 1)
● Para la estimación final dividimos las k variables en grupos y hacemos el promedio de cada grupo tomando luego la media de los promedios.
DGIM
● Consideramos Streams binarios.
● Tomamos una ventana fija de “m” bits con m realmente muy grande y queremos calcular cuántos bits en 1 vimos en los últimos k bits con k<=m.
● Es importante remarcar dos cosas:
- n es un número muy grande por lo que no podemos simplemente almacenar los últimos n bits
- Para un n fijo debemos poder calcular la cantidad de unos para cualquier k <= n, no solo para la ventana completa.
● Para esto utilizaremos DGIM.
● Sobre la ventana de m bits el algoritmo va a mantener k sub-ventanas que no pueden superponerse.
● Por cada sub-ventana va a llevar 2 valores: la posición en la ventana donde comienza la sub-ventana y la cantidad de unos que hay en la misma.
● Por cada bit procesado a la posición de cada sub-ventana le sumamos uno (para mantener el offset)
● Procesamos bit por bit el stream, si el bit es 0 lo ignoramos completamente.
● Si el bit es 1 entonces creamos una ventana de tamaño 1 para ese bit con contador = 1.
● Luego debemos analizar cuantas sub-ventanas hay con 1 bit en total.
● Si hay 1 o 2 no hacemos nada.
● Si hay 3 entonces combinamos las dos sub-ventanas mas viejas en una nueva sub-ventana de 2 bits.
● Y luego vemos cuantas sub-ventanas de 2 bits hay
● Si hay 1 o 2 no hacemos nada.
● Si hay 3 entonces combinamos las dos sub-ventanas mas viejas en una nueva sub-ventana de 4 bits.
● Y así sucesivamente…
Decaying Windows
● Otra alternativa para calcular cuántos 1s parecen en los últimos n bits de un stream
● Aplica una función que vaya decayendo el peso de cada bit en 1 ya observado a medida que procesamos el stream.
● Si nos interesan los últimos “n” bits del stream entonces usamos una constante c = 10-n, llevamos un contador que comienza en 0 y por cada bit del stream multiplicamos el contador por 1-c y luego sumamos el bit (1 o 0).
Bloom Filters: objetivo
Dado un stream queremos saber si los elementos que observamos en el mismo pertenecen o no a un cierto conjunto de elementos predefinidos.
Bloom Filters
○ Contamos con un vector binario de “m” bits y k funciónes de hashing 0..m.
○ Para “agregar” un elemento al filtro le aplicamos las funciones de hashing y luego encendemos en 1 los bits apuntados por las funciones.
○ Se prenden k o menos bits según haya o no colisiones
Bloom Filters. Para valores de n y m fijos, como se calcula el valor optimo de k?
k = (m/n) log 2
Si usamos el k óptimo entonces la cantidad de bits a usar puede calcularse como: m = n ln(p) / (ln 2)^2
donde p: probabilidad que queremos para un falso positivo
