Algoritmo de transmisión

Clase de algoritmos que operan sobre flujos de datos

En informática , los algoritmos de streaming 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 unos pocos pasos, normalmente solo uno . Estos algoritmos están diseñados para funcionar 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 restricciones, 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] 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 un artículo de 1996 de Noga Alon , Yossi Matias y Mario Szegedy . ^[3] Por este artículo, los autores ganaron más tarde el Premio Gödel en 2005 "por su contribución fundamental a los algoritmos de streaming". Desde entonces, ha habido una gran cantidad de trabajo centrado en los algoritmos de streaming de datos que abarca un espectro diverso de campos de la ciencia informática, como la teoría, las bases de datos, las redes y el procesamiento del lenguaje natural.

Los algoritmos de semi-transmisión se introdujeron en 2005 como una relajación de los algoritmos de transmisión 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 todavía es significativa para grafos densos y puede resolver problemas interesantes (como la conectividad) que son insolubles en el espacio. ${\displaystyle o(n)}$

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 números enteros (de algún dominio finito) que generalmente no está disponible para acceso aleatorio , sino que llega de a uno por vez en un "flujo". ^[5] Si el flujo tiene una longitud n y el dominio tiene un tamaño m , los algoritmos generalmente están restringidos a usar un espacio que sea logarítmico en m y n . Por lo general, solo pueden realizar una pequeña cantidad constante de pasadas sobre el flujo, a veces solo una . ^[6]

Modelos de torniquetes y cajas registradoras

Gran parte de la literatura sobre streaming 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 (inicializado en el vector cero ) al que se le presentan actualizaciones en un flujo. El objetivo de estos algoritmos es calcular funciones de usando considerablemente menos espacio del que se necesitaría para representarlas con precisión. Existen dos modelos comunes para actualizar dichos flujos, denominados modelos de "caja registradora" y de "torniquete". ^[7] ${\displaystyle \mathbf {a} =(a_{1},\dots ,a_{n})}$ ${\displaystyle \mathbf {0} }$ ${\displaystyle \mathbf {a} }$ ${\displaystyle \mathbf {a} }$

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

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

Modelo de ventana corrediza

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

Además de los problemas basados ​​en frecuencias mencionados anteriormente, también se han estudiado otros tipos de problemas. Muchos problemas de grafos se resuelven en un contexto en el que la matriz de adyacencia o la lista de adyacencias del grafo se transmite en un orden desconocido. También hay algunos problemas que dependen en gran medida del orden de la transmisión (es decir, funciones asimétricas), como contar el número de inversiones en una transmisión y encontrar la subsecuencia creciente más larga. ^{[ cita requerida ]}

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.
• 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 una memoria limitada disponible, pero pueden diferir 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 se expresa a menudo como una aproximación, lo que significa que el algoritmo logra un error de menos de con una probabilidad . ${\displaystyle (\epsilon ,\delta )}$ ${\displaystyle \epsilon }$ ${\displaystyle 1-\delta }$

Aplicaciones

Los algoritmos de streaming tienen varias aplicaciones en redes , como por ejemplo, la monitorización de enlaces de red en busca de flujos de elefantes , el conteo del número de flujos distintos, la estimación de la distribución de tamaños de flujo, etc. ^[8] También tienen aplicaciones en bases de datos, como la estimación del tamaño de una unión ^{[ cita requerida ]} .

Algunos problemas de transmisión

Momentos de frecuencia

El momento de frecuencia k de un conjunto de frecuencias se define como . ${\displaystyle \mathbf {a} }$ ${\displaystyle 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 las propiedades estadísticas de los datos, como el coeficiente de variación de Gini. se define como la frecuencia de los elementos más frecuentes. ${\displaystyle F_{1}}$ ${\displaystyle F_{2}}$ ${\displaystyle F_{\infty }}$

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

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 ∈ (1,2,3,4,..., N ) que requiere al menos una memoria de orden . ^[3] Pero tenemos limitaciones de espacio y requerimos un algoritmo que calcule en una memoria mucho menor. 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] ${\displaystyle \Omega (N)}$

Calculador F₀(elementos distintos en un DataStream)

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 reemplazarse por un contador log n que puede almacenarse en log log n bits. ^[12] Flajolet et al. en ^[2] mejoraron este método utilizando una función hash h que se supone que distribuye uniformemente el elemento en el espacio hash (una cadena binaria de longitud L ).

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

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

${\displaystyle 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 . ${\displaystyle \rho (y)}$ ${\displaystyle \rho (0)}$

${\displaystyle \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 flujo de datos de longitud M cuya cardinalidad se debe determinar. Sea BITMAP [0... L − 1] el

espacio hash donde se registran los ρ ( valores hash ). El algoritmo siguiente 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 terminar 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.

• Entonces BITMAP [ i ] es ciertamente 0 ${\displaystyle i\gg \log(N)}$
• Entonces BITMAP [ i ] es ciertamente 1 ${\displaystyle i\ll \log(N)}$
• Para entonces BITMAP [ i ] es una franja de 0 y 1. ${\displaystyle 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, según ellos, distribuye uniformemente los valores hash en el espacio hash.

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

Procedimiento 2 Valor mínimo KInicializar 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 terminar sifin paradevuelve t/Max(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. Existen valores hash del orden . El tiempo de acceso se puede reducir si almacenamos los valores hash t en un árbol binario. De esta forma la complejidad temporal se reducirá a . ${\displaystyle O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)}$ ${\displaystyle O(\log(m))}$ ${\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}$ ${\displaystyle O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)}$

CalculadorQue me _jodas

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. Luego, construyamos una variable aleatoria X de la siguiente manera:

• Seleccione un _p que sea un miembro aleatorio de la secuencia A con índice en p , ${\displaystyle a_{p}=l\in (1,2,3,\ldots ,n)}$
• Sea , representa el número de ocurrencias de l dentro de los miembros de la secuencia A después de un _p . ${\displaystyle r=|\{q:q\geq p,a_{q}=l\}|}$
• Variable aleatoria . ${\displaystyle 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 como salida la mediana . Donde Y _i es el promedio de X _ij donde 1 ≤ j ≤ S ₁ . ${\displaystyle O(n^{1-1/k}/\lambda ^{2})}$ ${\displaystyle O(\log(1/\varepsilon ))}$ ${\displaystyle Y_{1},Y_{2},...,Y_{S2}}$ ${\displaystyle Y}$

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

${\displaystyle {\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 deQue me _jodas

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 ⁠ ⁠ ${\displaystyle S_{1}*S_{2}}$ .

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

Un enfoque más sencillo para calcularF2_​

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

Esto reduce aún más la complejidad del cálculo . ${\displaystyle F_{2}}$ ${\displaystyle 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 constituyen 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 una mayoría del flujo.

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

Algunos algoritmos notables son:

• Algoritmo de votación mayoritaria de Boyer-Moore
• Boceto del conde Min
• Conteo con pérdida
• Filtros Bloom de múltiples etapas
• Algoritmo de peso pesado de Misra-Gries
• Resumen de Misra-Gries

Detección de eventos

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

Contando elementos distintos

Contar el número de elementos distintos en una secuencia (a veces llamado el momento F ₀ ) 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 ( ε ² + log d ) , con tiempos de actualización y reporte de O (1) en el peor de los casos, así como funciones hash universales y una familia hash independiente r -wise donde r = Ω(log(1/ ε ) / log log(1/ ε )) .

Entropía

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

Aprendizaje en línea

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

• Hashing de características
• Descenso de gradiente estocástico

Límites inferiores

Se han calculado límites inferiores para muchos de los problemas de transmisión de datos que se han estudiado. Sin lugar a dudas, la técnica más común para calcular estos límites inferiores ha sido el uso de la complejidad de la comunicación . ^{[ cita requerida ]}

Véase también

• Minería de flujo de datos
• Agrupamiento de flujos de datos
• Algoritmo en línea
• Procesamiento de flujo
• Algoritmo secuencial

Notas

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.
2. Flajolet y Martín (1985) harvtxt error: no target: CITEREFFlajoletMartin1985 (help)
3. Alon, Matías y Szegedy (1996)
4. Feigenbaum, Joan; Sampath, Kannan (2005). "Sobre problemas de grafos en un modelo de semi-transmisión". Ciencias de la Computación Teórica . 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-1581135077.S2CID2071130  .​
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 . Apuntes 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-3540457268.S2CID 4684185  .
7. Gilbert y otros (2001)
8. Xu (2007)
9. 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 la ACM sobre teoría de la computación . STOC '05. Nueva York, NY, EE. UU.: ACM. pp. 202–208. doi :10.1145/1060590.1060621. ISBN 978-1-58113-960-0. Número de identificación del sujeto  7911758.
10. Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca (13 de septiembre de 2002). Rolim, José DP; Vadhan, Salil (eds.). Conteo de elementos distintos en un flujo de datos . Notas de clase en informática. Springer Berlin 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  .
11. Morris (1978)
12. Flajolet, Philippe (1985-03-01). "Recuento 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). "Resúmenes de Misra-Gries". En Kao, Ming-Yang (ed.). Enciclopedia de algoritmos . Springer US. págs. 1–5. doi :10.1007/978-3-642-27848-8_572-1. ISBN . 9783642278488.
14. Schubert, E.; Weiler, M.; Kriegel, HP (2014). SigniTrend: detección escalable de temas emergentes en secuencias textuales mediante umbrales de significación 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 9781450329569.
15. 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 por primera vez como Alon, Noga; Matias, 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, Número de identificación del sujeto  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-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), "Surfing de wavelets en secuencias: resúmenes de una sola pasada 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 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.S2CID10006932  .​.
• Karp, RM ; Papadimitriou, CH ; Shenker, S. (2003), "Un algoritmo simple para encontrar elementos frecuentes en secuencias 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) (PDF) , pág. 145, doi :10.1145/1140277.1140295, hdl : 1802/2537 , ISBN 978-1595933195, S2CID240982 ​^{[ enlace muerto permanente ]} .
• Xu, Jun (Jim) (2007), Un 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 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), "Conteo de grandes cantidades de eventos en registros pequeños", Communications of the ACM , 21 (10): 840–842, doi : 10.1145/359619.359627 , S2CID  36226357.