Algoritmo de transmisión

En informática , los algoritmos de transmisión son algoritmos para procesar flujos de datos en los que la entrada se presenta como una secuencia de elementos y se puede examinar en solo unas pocas pasadas, generalmente solo una . Estos algoritmos están diseñados para operar con memoria limitada, generalmente logarítmica en el tamaño del flujo y/o en el valor máximo del flujo, y también pueden tener un tiempo de procesamiento limitado por elemento.

Como resultado de estas limitaciones, los algoritmos de transmisión a menudo producen respuestas aproximadas basadas en un resumen o "bosquejo" del flujo de datos.

Historia

Aunque los algoritmos de streaming ya habían sido estudiados por Munro y Paterson ^[1] ya en 1978, así como por Philippe Flajolet y G. Nigel Martin en 1982/83, ^[2] el campo de los algoritmos de streaming se formalizó y popularizó por primera vez en 1996. artículo de Noga Alon , Yossi Matias y Mario Szegedy . ^[3] Por este artículo, los autores ganaron posteriormente el Premio Gödel en 2005 "por su contribución fundamental a los algoritmos de transmisión". Desde entonces, ha habido una gran cantidad de trabajo centrado en algoritmos de transmisión de datos que abarca un espectro diverso de campos de la informática, como la teoría, las bases de datos, las redes y el procesamiento del lenguaje natural.

Los algoritmos de semi-streaming se introdujeron en 2005 como una relajación de los algoritmos de streaming para gráficos, ^[4] en los que el espacio permitido es lineal en el número de vértices n , pero sólo logarítmico en el número de aristas m . Esta relajación sigue siendo significativa para gráficos densos y puede resolver problemas interesantes (como la conectividad) que son insolubles en el espacio. $o(n)$

Modelos

Modelo de flujo de datos

En el modelo de flujo de datos, parte o toda la entrada se representa como una secuencia finita de números enteros (de algún dominio finito) que generalmente no está disponible para acceso aleatorio , sino que llega uno a la vez en un "flujo". ^[5] Si la secuencia tiene una longitud n y el dominio tiene un tamaño m , los algoritmos generalmente están restringidos a utilizar un espacio logarítmico en m y n . Por lo general, sólo pueden realizar un pequeño número constante de pasadas sobre el arroyo, a veces sólo una . ^[6]

Modelos de torniquete y caja registradora.

Gran parte de la literatura sobre streaming se ocupa de calcular estadísticas sobre distribuciones de frecuencia que son demasiado grandes para almacenarse. Para esta clase de problemas, hay un vector (inicializado en el vector cero ) al que se le presentan actualizaciones en una secuencia. El objetivo de estos algoritmos es calcular funciones utilizando considerablemente menos espacio del que se necesitaría para representar con precisión. Hay dos modelos comunes para actualizar dichos flujos, llamados modelos de "caja registradora" y "torniquete". ^[7] $\mathbf {a} =(a_{1},\dots,a_{n})$ $\mathbf {0}$ $\mathbf {a}$ $\mathbf {a}$

En el modelo de caja registradora, cada actualización tiene la forma , por lo que se incrementa en algún número entero positivo . Un caso especial notable es cuando (solo se permiten inserciones de unidades). $\langle i,c\rangle$ ${\ Displaystyle a_ {i}}$ $c$ $c=1$

En el modelo de torniquete, cada actualización tiene la forma , por lo que se incrementa en algún número entero (posiblemente negativo) . En el modelo de "torniquete estricto", ningún en ningún momento puede ser menor que cero. $\langle i,c\rangle$ ${\ Displaystyle a_ {i}}$ $c$ ${\ Displaystyle a_ {i}}$

Modelo de ventana corredera

Varios artículos también consideran el modelo de "ventana deslizante". ^{[ cita necesaria ]} En este modelo, la función de interés es calcular en una ventana de tamaño fijo en la secuencia. A medida que avanza la transmisión, los elementos del final de la ventana se eliminan de la consideración mientras que nuevos elementos de la transmisión toman su lugar.

Además de los problemas anteriores basados en la frecuencia, también se han estudiado otros tipos de problemas. Muchos problemas de gráficos se resuelven en entornos donde la matriz de adyacencia o la lista de adyacencia del gráfico se transmiten en algún orden desconocido. También hay algunos problemas que dependen mucho del orden de la secuencia (es decir, funciones asimétricas), como contar el número de inversiones en una secuencia y encontrar la subsecuencia creciente más larga. ^{[ cita necesaria ]}

Evaluación

El rendimiento de un algoritmo que opera sobre flujos de datos se mide mediante tres factores básicos:

El número de pases que el algoritmo debe realizar sobre la secuencia.
La memoria disponible.
El tiempo de ejecución del algoritmo.

Estos algoritmos tienen muchas similitudes con los algoritmos en línea, ya que ambos requieren que se tomen decisiones antes de que todos los datos estén disponibles, pero no son idénticos. Los algoritmos de flujo de datos solo tienen memoria limitada disponible, pero pueden posponer la acción hasta que llegue un grupo de puntos, mientras que los algoritmos en línea deben actuar tan pronto como llegue cada punto.

Si el algoritmo es un algoritmo de aproximación, entonces la precisión de la respuesta es otro factor clave. La precisión a menudo se expresa como una aproximación, lo que significa que el algoritmo logra un error menor que con la probabilidad . $(\épsilon,\delta)$ ${\displaystyle\epsilon}$ $1-\delta$

Aplicaciones

Los algoritmos de transmisión tienen varias aplicaciones en redes , como monitorear los enlaces de red para detectar flujos de elefantes , contar el número de flujos distintos, estimar la distribución de los tamaños de los flujos, etc. ^[8] También tienen aplicaciones en bases de datos, como estimar el tamaño de una unión ^{[ cita necesaria ]} .

Algunos problemas de transmisión

Momentos de frecuencia

El $k$ -ésimo momento de frecuencia de un conjunto de frecuencias se define como . $\mathbf {a}$ $F_{k}(\mathbf {a} )=\sum _ {i=1}^{n}a_{i}^{k}$

El primer momento es simplemente la suma de las frecuencias (es decir, el recuento total). El segundo momento es útil para calcular propiedades estadísticas de los datos, como el coeficiente de variación de Gini. se define como la frecuencia de los ítems más frecuentes. ${\ Displaystyle F_ {1}}$ ${\ Displaystyle F_ {2}}$ $F_{\infty }$

El artículo fundamental de Alon, Matias y Szegedy abordó el problema de estimar los momentos de frecuencia. ^{[ cita necesaria ]}

Calcular momentos de frecuencia.

Un enfoque directo para encontrar los momentos de frecuencia requiere mantener un registro $m i$ para todos los elementos distintos $a i \in (1,2,3,4,..., N)$ que requiere al menos memoria de orden . ^[3] Pero tenemos limitaciones de espacio y necesitamos un algoritmo que calcule en mucha menos memoria. Esto se puede lograr utilizando aproximaciones en lugar de valores exactos. Un algoritmo que calcula una aproximación ( ε,δ ) de $F$ $k$ , donde $F'$ $k$ es el valor aproximado ( ε,δ ) de $F$ $k$ . ^[9] Donde ε es el parámetro de aproximación y δ es el parámetro de confianza. ^[10] $\Omega (N)$

Calcular F ₀ (elementos distintos en un DataStream)

Algoritmo de boceto FM

Flajolet et al. en ^[2] introdujo el método probabilístico de conteo que se inspiró en un artículo de Robert Morris . ^[11] Morris en su artículo dice que si se elimina el requisito de precisión, un contador n puede reemplazarse por un contador $log n$ que puede almacenarse en $log log n$ bits. ^[12] Flajolet et al. en ^[2] mejoró este método mediante el uso de una función hash $h$ que se supone que distribuye uniformemente el elemento en el espacio hash (una cadena binaria de longitud $L$ ).

h:[m]\rightarrow [0,2^{L}-1]

Sea $bit(y,k)$ el k-ésimo bit en representación binaria de $y$

y=\sum _{k\geq 0}\mathrm {bit} (y,k)*2^{k}

Let representa la posición del bit menos significativo en la representación binaria de $y$ $i$ con una convención adecuada para . $\rho (y)$ $\rho (0)$

\rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}

Sea A la secuencia de un flujo de datos de longitud M cuya cardinalidad debe determinarse. Sea BITMAP [0... L − 1] el

espacio hash donde se registran los $ρ$ ( valores hash ). El siguiente algoritmo determina la cardinalidad aproximada de A.

Procedimiento FM-Sketch: para i en 0 a L − 1 hacer MAPA DE BITS[i] := 0 fin para para x en A: hacer Índice := ρ(hash(x)) si BITMAP[índice] = 0 entonces MAPA DE BITS[índice] := 1 terminara si fin para B: = Posición del bit 0 más a la izquierda de BITMAP[] volver 2^B

Si hay N elementos distintos en un flujo de datos.

Entonces BITMAP [ i ] es ciertamente 0 $i\gg \log(N)$
Entonces BITMAP [ i ] es ciertamente 1 $i\ll \log(N)$
Entonces BITMAP [ i ] es una franja de 0 y 1 $i\approx \log(N)$

K -algoritmo de valor mínimo

El algoritmo anterior describe el primer intento de Flajolet y Martin de aproximar F ₀ en el flujo de datos. Su algoritmo elige una función hash aleatoria que suponen distribuye uniformemente los valores hash en el espacio hash.

Bar-Yossef et al. en ^[10] se introdujo el algoritmo de valor mínimo k para determinar el número de elementos distintos en el flujo de datos. Usaron una función hash h similar que se puede normalizar a [0,1] como . Pero fijaron un límite t para el número de valores en el espacio hash. El valor de t se supone del orden (es decir, menos valor de aproximación ε requiere más t ). El algoritmo KMV mantiene solo t los valores hash más pequeños en el espacio hash. Una vez que han llegado todos los m valores de la corriente, se utiliza para calcular . Es decir, en un espacio hash casi uniforme, esperan que al menos t elementos sean menores que . $h:[m]\rightarrow [0,1]$ $O\left({\dfrac {1}{\varepsilon _{2}}}\right)$ $\upsilon =\mathrm {Max} (h(a_{i}))$ $F'_{0}={\dfrac {t}{\upsilon }}$ $O\left({\dfrac {t}{F_{0}}}\right)$

Procedimiento 2 K-Valor MínimoInicialice los primeros valores t de KMVpara un en a1 a un hacer si h(a) < Max(KMV) entonces Eliminar Max (KMV) del conjunto KMV Insertar h(a) en KMV terminara sifin pararetorno t/máx.(KMV)

Análisis de complejidad de KMV.

El algoritmo KMV se puede implementar en el espacio de bits de memoria. Cada valor hash requiere espacio de bits de memoria de orden. Hay valores hash del orden . El tiempo de acceso se puede reducir si almacenamos los valores hash t en un árbol binario. Por tanto, la complejidad del tiempo se reducirá a . $O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)$ $O(\log(m))$ $O\left({\dfrac {1}{\varepsilon _{2}}}\right)$ $O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)$

Calculando $F k$

Alon et al. estima $F k$ definiendo variables aleatorias que se pueden calcular dentro de un espacio y tiempo dados. ^[3] El valor esperado de las variables aleatorias da el valor aproximado de $F k$ .

Supongamos que la longitud de la secuencia m se conoce de antemano. Luego construya una variable aleatoria X de la siguiente manera:

Seleccione $a p$ para que sea un miembro aleatorio de la secuencia $A$ con índice en $p$ , $a_{p}=l\in (1,2,3,\ldots ,n)$
Sea , representa el número de apariciones de $l$ dentro de los miembros de la secuencia $A$ que sigue $a$ $p$ . $r=|\{q:q\geq p,a_{q}=l\}|$
Variable aleatoria . $X=m(r^{k}-(r-1)^{k})$

Supongamos que S ₁ es del orden y S ₂ es del orden . El algoritmo toma la variable aleatoria S ₂ y genera la mediana . Donde $Y$ $i$ es el promedio de $X$ $ij$ donde 1 ≤ j ≤ S ₁ . $O(n^{1-1/k}/\lambda ^{2})$ $O(\log(1/\varepsilon ))$ $Y_{1},Y_{2},...,Y_{S2}$ $Y$

Ahora calcule la expectativa de la variable aleatoria $E (X)$ .

{\begin{array}{lll}E(X)&=&\sum _{i=1}^{n}\sum _{i=1}^{m_{i}}(j^{k}-(j-1)^{k})\\&=&{\frac {m}{m}}[(1^{k}+(2^{k}-1^{k})+\ldots +(m_{1}^{k}-(m_{1}-1)^{k}))\\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{2}^{k}-(m_{2}-1)^{k}))+\ldots \\&&\;+\;(1^{k}+(2^{k}-1^{k})+\ldots +(m_{n}^{k}-(m_{n}-1)^{k}))]\\&=&\sum _{i=1}^{n}m_{i}^{k}=F_{k}\end{array}}

Complejidad de $F k$

Del algoritmo para calcular $F k$ discutido anteriormente, podemos ver que cada variable aleatoria $X$ almacena el valor de $a p$ y $r$ . Entonces, para calcular $X$ necesitamos mantener solo $log(n)$ bits para almacenar $ap$ y $log$ $(n)$ bits para almacenar $r$ . El número total de variable aleatoria $X$ será el . $S_{1}*S_{2}$

Por lo tanto, la complejidad espacial total que toma el algoritmo es del orden de $O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)$

Enfoque más simple para calcular $F 2$

El algoritmo anterior calcula en orden de bits de memoria. Alon et al. en ^[3] simplificó este algoritmo utilizando una variable aleatoria independiente de cuatro factores con valores asignados a . $F_{2}$ $O({\sqrt {n}}(\log m+\log n))$ $\{-1,1\}$

Esto reduce aún más la complejidad de calcular a $F_{2}$ $O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)$

Elementos frecuentes

En el modelo de flujo de datos, el problema frecuente de los elementos es generar un conjunto de elementos que constituyan más que una fracción fija del flujo. Un caso especial es el problema de la mayoría , que consiste en determinar si algún valor constituye o no la mayoría del flujo.

Más formalmente, fije alguna constante positiva c > 1, sea m la longitud de la corriente y sea f _i la frecuencia de valor i en la corriente. El problema frecuente de los elementos es generar el conjunto { i | f _i > m/c }. ^[13]

Algunos algoritmos notables son:

Detección de eventos

La detección de eventos en flujos de datos a menudo se realiza utilizando un algoritmo de gran impacto como el enumerado anteriormente: los elementos más frecuentes y su frecuencia se determinan usando uno de estos algoritmos, luego el mayor aumento con respecto al punto de tiempo anterior se informa como tendencia. Este enfoque se puede perfeccionar utilizando medias móviles ponderadas exponencialmente y varianza para la normalización. ^[14]

Contando elementos distintos

Contar el número de elementos distintos en una corriente (a veces llamado momento $F 0$ ) es otro problema que ha sido bien estudiado. El primer algoritmo fue propuesto por Flajolet y Martin. En 2010, Daniel Kane , Jelani Nelson y David Woodruff encontraron un algoritmo asintóticamente óptimo para este problema. ^[15] Utiliza espacio $O (ε 2 + log d) , con tiempos de informe y actualización en el peor de los casos$ $O (1)$ , así como funciones hash universales y una familia hash independiente de $r donde$ $r = Ω(log(1) / ε) / log log(1/ ε))$ .

entropía

La entropía (empírica) de un conjunto de frecuencias se define como , donde . $\mathbf {a}$ $F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i}}{m}}$ $m=\sum _{i=1}^{n}a_{i}$

Aprender en línea

Aprenda un modelo (por ejemplo, un clasificador ) con una sola pasada sobre un conjunto de entrenamiento.

límites inferiores

Se han calculado límites inferiores para muchos de los problemas de transmisión de datos que se han estudiado. Con diferencia, la técnica más común para calcular estos límites inferiores ha sido utilizar la complejidad de la comunicación . ^{[ cita necesaria ]}

Ver también

Notas

^ Munro, J. Ian; Paterson, Mike (1978). "Selección y clasificación con almacenamiento limitado". XIX Simposio anual sobre fundamentos de la informática, Ann Arbor, Michigan, EE. UU., 16 a 18 de octubre de 1978 . Sociedad de Computación IEEE. págs. 253–258. doi :10.1109/SFCS.1978.32.
^ abc Flajolet y Martín (1985)
^ abcd Alon, Matías y Szegedy (1996)
^ Feigenbaum, Juana; Sampath, Kannan (2005). "Sobre problemas de gráficos en un modelo semi-streaming". Informática Teórica . 348 (2): 207–216. doi : 10.1016/j.tcs.2005.09.013 .
^ Babcock, Brian; Babú, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). "Modelos y problemas en los sistemas de flujo de datos". Actas del vigésimo primer simposio ACM SIGMOD-SIGACT-SIGART sobre principios de sistemas de bases de datos . VAINAS '02. Nueva York, NY, Estados Unidos: ACM. págs. 1–16. CiteSeerX 10.1.1.138.190 . doi :10.1145/543613.543615. ISBN 978-1581135077. S2CID 2071130.
^ Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (13 de septiembre de 2002). "Contar elementos distintos en un flujo de datos". Técnicas de aleatorización y aproximación en informática . Apuntes de conferencias sobre informática. vol. 2483. Springer, Berlín, Heidelberg. págs. 1–10. CiteSeerX 10.1.1.12.6276 . doi :10.1007/3-540-45726-7_1. ISBN 978-3540457268. S2CID 4684185.
^ Gilbert y col. (2001)
^ Xu (2007)
^ Indyk, Piotr; Woodruff, David (1 de enero de 2005). "Aproximaciones óptimas de los momentos de frecuencia de los flujos de datos". Actas del trigésimo séptimo simposio anual de ACM sobre teoría de la informática . STOC '05. Nueva York, NY, Estados Unidos: ACM. págs. 202-208. doi :10.1145/1060590.1060621. ISBN 978-1-58113-960-0. S2CID 7911758.
^ ab Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (13 de septiembre de 2002). Rolim, José DP; Vadhan, Salil (eds.). Contar elementos distintos en un flujo de datos . Apuntes de conferencias sobre informática. Springer Berlín Heidelberg. págs. 1–10. CiteSeerX 10.1.1.12.6276 . doi :10.1007/3-540-45726-7_1. ISBN 978-3-540-44147-2. S2CID 4684185.
^ Morris (1978)
^ Flajolet, Philippe (1 de marzo de 1985). "Recuento aproximado: un análisis detallado". BIT Matemáticas Numéricas . 25 (1): 113-134. CiteSeerX 10.1.1.64.5320 . doi :10.1007/BF01934993. ISSN 0006-3835. S2CID 2809103.
^ Cormode, Graham (2014). "Resúmenes de Misra-Gries". En Kao, Ming-Yang (ed.). Enciclopedia de algoritmos . Springer Estados Unidos. págs. 1 a 5. doi :10.1007/978-3-642-27848-8_572-1. ISBN 9783642278488.
^ Schubert, E.; Weiler, M.; Kriegel, HP (2014). SigniTrend: detección escalable de temas emergentes en flujos textuales mediante umbrales de importancia hash . Actas de la vigésima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos - KDD '14. págs. 871–880. doi :10.1145/2623330.2623740. ISBN 9781450329569.
^ Kane, Nelson y Woodruff (2010)

Referencias

Alón, Noga ; Matías, Yossi ; Szegedy, Mario (1999), "La complejidad espacial de la aproximación de los momentos de frecuencia", Journal of Computer and System Sciences , 58 (1): 137–147, doi : 10.1006/jcss.1997.1545 , ISSN 0022-0000. Publicado por primera vez como Alon, Noga; Matías, Yossi; Szegedy, Mario (1996), "La complejidad espacial de la aproximación de los momentos de frecuencia", Actas del 28º Simposio ACM sobre Teoría de la Computación (STOC 1996) , págs. 20-29, CiteSeerX 10.1.1.131.4984 , doi :10.1145/ 237814.237823, ISBN 978-0-89791-785-8, S2CID 1627911.
Babcock, Brian; Babú, Shivnath; Datar, Mayur; Motwani, Rajeev ; Widom, Jennifer (2002), "Modelos y problemas en sistemas de flujo de datos", Actas del 21º Simposio ACM SIGMOD-SIGACT-SIGART sobre principios de sistemas de bases de datos (PODS 2002) (PDF) , págs. 1–16, CiteSeerX 10.1. 1.138.190 , doi : 10.1145/543613.543615, ISBN 978-1581135077, S2CID 2071130, archivado desde el original (PDF) el 9 de julio de 2017 , consultado el 15 de julio de 2013.
Gilbert, AC ; Kotidis, Y.; Muthukrishnan, S .; Strauss, MJ (2001), "Navegación por ondas en transmisiones: resúmenes de un solo paso para consultas agregadas aproximadas" (PDF) , Actas de la conferencia internacional sobre bases de datos muy grandes : 79–88.
Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). "Un algoritmo óptimo para el problema de los distintos elementos". Actas del vigésimo noveno simposio ACM SIGMOD-SIGACT-SIGART sobre principios de sistemas de bases de datos . VAINAS '10. Nueva York, NY, Estados Unidos: ACM. págs. 41–52. CiteSeerX 10.1.1.164.142 . doi :10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. S2CID 10006932..
Karp, RM ; Papadimitriou, CH ; Shenker, S. (2003), "Un algoritmo simple para encontrar elementos frecuentes en flujos y bolsas", ACM Transactions on Database Systems , 28 (1): 51–55, CiteSeerX 10.1.1.116.8530 , doi :10.1145/762471.762473, S2CID 952840.
Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, junio; Zhang, Hui (2006), "Algoritmos de transmisión de datos para estimar la entropía del tráfico de red", Actas de la Conferencia internacional conjunta sobre medición y modelado de sistemas informáticos (ACM SIGMETRICS 2006) (PDF) , p. 145, doi :10.1145/1140277.1140295, hdl : 1802/2537 , ISBN 978-1595933195, S2CID 240982^{[ enlace muerto permanente ]} .
Xu, Jun (Jim) (2007), Tutorial sobre transmisión de datos en red (PDF).
Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., "Learning Nested Concepts With Limited Storage", Actas IJCAI'91 de la 12ª conferencia internacional conjunta sobre inteligencia artificial - Volumen 2, páginas 777–782, Morgan Kaufmann Publishers Inc. San Francisco, CA, EE. UU. ©1991
Morris, Robert (1978), "Contando una gran cantidad de eventos en registros pequeños", Comunicaciones de la ACM , 21 (10): 840–842, doi : 10.1145/359619.359627 , S2CID 36226357.