Algoritmo de transmisión

En informática , los algoritmos de procesamiento en flujo procesan flujos de datos de entrada como una secuencia de elementos, realizando normalmente una sola pasada (o unas pocas) a través de los datos. Estos algoritmos están diseñados para operar con memoria limitada, generalmente con una dependencia logarítmica del tamaño del flujo y/o del valor máximo del mismo, y también pueden tener un tiempo de procesamiento limitado por elemento.

Como resultado de estas limitaciones, los algoritmos de procesamiento de datos en tiempo real suelen producir respuestas aproximadas basadas en un resumen o "boceto" del flujo de datos.

Historia

Aunque Munro y Paterson ya habían estudiado los algoritmos de transmisión ^{[ 1 ]} en 1978, así como Philippe Flajolet y G. Nigel Martin en 1982/83, ^{[ 2 ]} el campo de los algoritmos de transmisión se formalizó y popularizó por primera vez en un artículo de 1996 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 un amplio corpus de trabajo centrado en los algoritmos de transmisión de datos que abarca un diverso espectro 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 grafos, ^{[ 4 ]} en los que el espacio permitido es lineal en el número de vértices n , pero solo logarítmico en el número de aristas m . Esta relajación sigue siendo significativa para grafos densos y puede resolver problemas interesantes (como la conectividad) que son insolubles en $o(n)$ espacio.

Modelos

Modelo de flujo de datos

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

Modelos de torniquetes y cajas registradoras

Gran parte de la literatura sobre procesamiento de datos en tiempo real se ocupa del cálculo de estadísticas sobre distribuciones de frecuencia que son demasiado grandes para ser almacenadas. Para esta clase de problemas, existe un vector $\mathbf {a} =(a_{1},\dots,a_{n})$ (inicializado al vector cero) $\mathbf {0}$ ) que recibe actualizaciones en un flujo. El objetivo de estos algoritmos es calcular funciones de $\mathbf {a}$ utilizando considerablemente menos espacio del que se necesitaría para representar $\mathbf {a}$ Precisamente. Existen dos modelos comunes para actualizar dichos flujos, denominados modelos de "caja registradora" y de "torniquete". ^{[ 7 ]}

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

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

Modelo de ventana corrediza

Varios artículos también consideran el modelo de "ventana deslizante". En este modelo, la función de interés se calcula sobre una ventana de tamaño fijo en el flujo de datos. A medida que el flujo avanza, los elementos del final de la ventana se eliminan y se incorporan nuevos elementos.

Además de los problemas basados en frecuencia mencionados anteriormente, también se han estudiado otros tipos de problemas. Muchos problemas de grafos se resuelven en un contexto donde la matriz de adyacencia o la lista de adyacencia del grafo se procesa en un orden desconocido. También existen problemas que dependen en gran medida del orden del procesamiento (es decir, funciones asimétricas), como contar el número de inversiones en un procesamiento y encontrar la subsecuencia creciente más larga.

Evaluación

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

El número de pasadas que el algoritmo debe realizar sobre el flujo de datos.
La memoria disponible.
El tiempo de ejecución del algoritmo.

Estos algoritmos presentan 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 disponen de memoria limitada, 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 llega 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 $(\épsilon,\delta)$ aproximación, lo que significa que el algoritmo logra un error menor que $\epsilon$ con probabilidad $1-\delta$ .

Aplicaciones

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

Algunos problemas de transmisión

Momentos de frecuencia

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

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

El artículo fundamental de Alon, Matias y Szegedy abordó el problema de la estimación de los momentos de frecuencia.

Cálculo de 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 $\Omega (N)$ . ^{[ 3 ]} Pero tenemos limitaciones de espacio y requerimos un algoritmo que calcule en mucha menos memoria. Esto se puede lograr usando 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 ]}

Cálculo de F ₀ (elementos distintos en un flujo de datos)

Algoritmo FM-Sketch

Flajolet et al. en ^{[ 2 ]} introdujeron un 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 ser reemplazado por un contador $log n$ que puede almacenarse en $log log n$ bits. ^{[ 12 ]} Flajolet et al. en ^{[ 2 ]} mejoraron este método usando 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 la representación binaria de $y.$

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

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

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

Sea A la secuencia de 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 entonces la cardinalidad aproximada de A.

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

Si hay N elementos distintos en un flujo de datos.

Para $i\gg \log(N)$ entonces BITMAP [ i ] es ciertamente 0
Para $i\ll \log(N)$ entonces BITMAP [ i ] es ciertamente 1
Para $i\approx \log(N)$ entonces BITMAP [ i ] es un conjunto de 0 y 1.

Algoritmo de valor mínimo K

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

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

Procedimiento 2 Valor mínimo K Inicializar los primeros valores t de KMV para un en a1 a un hacer si h(a) < Max(KMV) entonces Eliminar Max(KMV) del conjunto KMV Insertar h(a) en KMV fin si fin para devolver t/Máx(KMV)

Análisis de complejidad de KMV

El algoritmo KMV se puede implementar en $O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)$ espacio de bits de memoria. Cada valor hash requiere espacio de orden $O(\log(m))$ bits de memoria. Hay valores hash del orden $O\left({\dfrac {1}{\varepsilon _{2}}}\right)$ El tiempo de acceso se puede reducir si almacenamos los valores hash t en un árbol binario . Por lo tanto, la complejidad temporal se reducirá a $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 pueden calcularse dentro de un espacio y tiempo determinados. ^{[ 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. Entonces, construyamos una variable aleatoria X de la siguiente manera:

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

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

Ahora calcula la esperanza 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 $a p$ y $log(n)$ bits para almacenar $r$ . El número total de variables aleatorias $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 sencillo para calcular $F 2$

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

Esto reduce aún más la complejidad del cálculo. $F_{2}$ a $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 de los elementos frecuentes consiste en generar un conjunto de elementos que representen más de 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.

De forma más formal, fijemos una constante positiva c > 1, sea m la longitud del flujo y sea f _i la frecuencia del valor i en el flujo. El problema de los elementos frecuentes consiste en generar el conjunto { i | f _i > m/c }. ^{[ 13 ]}

Algunos algoritmos destacados son:

Detección de eventos

La detección de eventos en flujos de datos se realiza a menudo mediante un algoritmo de elementos frecuentes como el descrito anteriormente: se determinan los elementos más frecuentes y su frecuencia utilizando uno de estos algoritmos, y luego se informa la mayor variación con respecto al punto temporal anterior como tendencia. Este enfoque se puede perfeccionar utilizando promedios móviles ponderados exponencialmente y varianza para la normalización. ^{[ 14 ]}

Contar elementos distintos

Contar el número de elementos distintos en un flujo (a veces llamado momento $F 0$ ) es otro problema que ha sido bien estudiado. El primer algoritmo para ello 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 un espacio $O (ε 2 + log d)$ , con tiempos de actualización e informe en el peor de los casos $O (1)$ , así como funciones hash universales y una familia hash independiente de $r$ elementos donde $r = Ω(log(1/ ε) / log log(1/ ε))$ .

Entropía

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

Aprendizaje en línea

Aprende 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. La técnica más común para calcular estos límites inferiores ha sido, con mucho, el uso de la complejidad de la comunicación .

Véase también

Notas

↑ Munro, J. Ian; Paterson, Mike (1978). "Selección y ordenación con almacenamiento limitado". 19º Simposio Anual sobre Fundamentos de la Informática, Ann Arbor, Michigan, EE. UU., 16-18 de octubre de 1978. IEEE Computer Society. págs. 253-258 . doi : 10.1109/SFCS.1978.32 .
1 2 3 Flajolet y Martin (1985)
1 2 3 4 Alon, Matías y Szegedy (1996)
↑ Feigenbaum, Joan; Sampath, Kannan (2005). "Sobre problemas de grafos en un modelo de semi-streaming" . Theoretical Computer Science . 348 (2): 207– 216. doi : 10.1016/j.tcs.2005.09.013 .
↑ Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). «Modelos y problemas en sistemas de flujo de datos». Actas del vigésimo primer simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de sistemas de bases de datos . PODS '02. Nueva York, NY, EE. UU.: ACM. págs. 1–16 . CiteSeerX 10.1.1.138.190 . doi : 10.1145/543613.543615 . ISBN 978-1-58113-507-7. S2CID 2071130 .
↑ Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (13 de septiembre de 2002). "Conteo de elementos distintos en un flujo de datos". Técnicas de aleatorización y aproximación en informática . Notas de clase en 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-3-540-45726-8. S2CID 4684185 .
↑ Gilbert et al. (2001)
↑ Xu (2007)
↑ Indyk, Piotr; Woodruff, David (1 de enero de 2005). «Aproximaciones óptimas de los momentos de frecuencia de flujos de datos». Actas del trigésimo séptimo simposio anual de la ACM sobre Teoría de la Computación . STOC '05. Nueva York, NY, EE. UU.: ACM. págs. 202–208 . doi : 10.1145/1060590.1060621 . ISBN 978-1-58113-960-0. S2CID 7911758 .
1 2 Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). Rolim, José DP; Vadhan, Salil (eds.). Counting Distinct Elements in a Data Stream . Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 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 (1985-03-01). "Conteo aproximado: Un análisis detallado". BIT Numerical Mathematics . 25 (1): 113– 134. CiteSeerX 10.1.1.64.5320 . doi : 10.1007/BF01934993 . ISSN 0006-3835 . S2CID 2809103 .
↑ Cormode, Graham (2014). «Resumen de Misra-Gries». En Kao, Ming-Yang (ed.). Enciclopedia de algoritmos . Springer US. pp. 1–5 . doi : 10.1007/978-3-642-27848-8_572-1 . ISBN 978-3-642-27848-8.
↑ Schubert, E.; Weiler, M.; Kriegel, HP (2014). SigniTrend: detección escalable de temas emergentes en flujos textuales mediante umbrales de significancia hash . Actas de la 20.ª 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 978-1-4503-2956-9.
↑ Kane, Nelson y Woodruff (2010)

Referencias

Alon, Noga ; Matias, 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 originalmente como Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), "The space complexity of approximating the frequency moments", Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996) , pp. 20–29 , CiteSeerX 10.1.1.131.4984 , doi : 10.1145/237814.237823 , ISBN 978-0-89791-785-8, S2CID 1627911 .
Babcock, Brian; Babu, 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-1-58113-507-7, S2CID 2071130 , archivado del original (PDF) el 09-07-2017 , recuperado el 15-07-2013 .
Flajolet, Philippe; Martin, G. Nigel (1985). "Algoritmos de conteo probabilístico para aplicaciones de bases de datos" (PDF) . Journal of Computer and System Sciences . 31 (2): 182– 209. doi : 10.1016/0022-0000(85)90041-8 . Recuperado el 11 de diciembre de 2016 .
Gilbert, AC ; Kotidis, Y.; Muthukrishnan, S .; Strauss, MJ (2001), "Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries" ( 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 elementos distintos». Actas del vigésimo noveno simposio ACM SIGMOD-SIGACT-SIGART sobre principios de sistemas de bases de datos . PODS '10. Nueva York, NY, EE. UU.: 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, Jun; 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) . pág. 145. doi : 10.1145/1140277.1140295 . hdl : 1802/2537 . ISBN 978-1-59593-319-5. S2CID 240982 . .
Xu, Jun (Jim) (2007), Tutorial sobre transmisión de datos en red (PDF).
Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., "Aprendizaje de conceptos anidados con almacenamiento limitado", Actas de la IJCAI'91, Actas 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), "Counting large numbers of events in small registers", Communications of the ACM , 21 (10): 840– 842, doi : 10.1145/359619.359627 , S2CID 36226357 .

[1] Munro, J. Ian; Paterson, Mike (1978). "Selección y ordenación con almacenamiento limitado". 19º Simposio Anual sobre Fundamentos de la Informática, Ann Arbor, Michigan, EE. UU., 16-18 de octubre de 1978. IEEE Computer Society. págs. 253-258 . doi : 10.1109/SFCS.1978.32 .

[:0-2] 1 2 3 Flajolet y Martin (1985)

[:1-3] 1 2 3 4 Alon, Matías y Szegedy (1996)

[4] Feigenbaum, Joan; Sampath, Kannan (2005). "Sobre problemas de grafos en un modelo de semi-streaming" . Theoretical Computer Science . 348 (2): 207– 216. doi : 10.1016/j.tcs.2005.09.013 .

[5] Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). «Modelos y problemas en sistemas de flujo de datos». Actas del vigésimo primer simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de sistemas de bases de datos . PODS '02. Nueva York, NY, EE. UU.: ACM. págs. 1–16 . CiteSeerX 10.1.1.138.190 . doi : 10.1145/543613.543615 . ISBN 978-1-58113-507-7. S2CID 2071130 .

[6] Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (13 de septiembre de 2002). "Conteo de elementos distintos en un flujo de datos". Técnicas de aleatorización y aproximación en informática . Notas de clase en 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-3-540-45726-8. S2CID 4684185 .

[turnstile-7] Gilbert et al. (2001)

[8] Xu (2007)

[9] Indyk, Piotr; Woodruff, David (1 de enero de 2005). «Aproximaciones óptimas de los momentos de frecuencia de flujos de datos». Actas del trigésimo séptimo simposio anual de la ACM sobre Teoría de la Computación . STOC '05. Nueva York, NY, EE. UU.: ACM. págs. 202–208 . doi : 10.1145/1060590.1060621 . ISBN 978-1-58113-960-0. S2CID 7911758 .

[:2-10] 1 2 Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (2002-09-13). Rolim, José DP; Vadhan, Salil (eds.). Counting Distinct Elements in a Data Stream . Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 1– 10. CiteSeerX 10.1.1.12.6276 . doi : 10.1007/3-540-45726-7_1 . ISBN 978-3-540-44147-2. S2CID 4684185 .

[11] Morris (1978)

[12] Flajolet, Philippe (1985-03-01). "Conteo aproximado: Un análisis detallado". BIT Numerical Mathematics . 25 (1): 113– 134. CiteSeerX 10.1.1.64.5320 . doi : 10.1007/BF01934993 . ISSN 0006-3835 . S2CID 2809103 .

[13] Cormode, Graham (2014). «Resumen de Misra-Gries». En Kao, Ming-Yang (ed.). Enciclopedia de algoritmos . Springer US. pp. 1–5 . doi : 10.1007/978-3-642-27848-8_572-1 . ISBN 978-3-642-27848-8.

[14] Schubert, E.; Weiler, M.; Kriegel, HP (2014). SigniTrend: detección escalable de temas emergentes en flujos textuales mediante umbrales de significancia hash . Actas de la 20.ª 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 978-1-4503-2956-9.

[15] Kane, Nelson y Woodruff (2010)

[ 1 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]