Algoritmo de flujo

Un algoritmo de transmisión es un algoritmo para procesar una secuencia de datos en uno o en un pequeño número de pases.

Los algoritmos de flujo resuelven problemas en los que los datos llegan secuencialmente y en gran volumen. Un ejemplo es el análisis del tráfico de red del lado del enrutador . Estos problemas imponen restricciones naturales sobre la memoria disponible (mucho menos que el tamaño de los datos de entrada) y el tiempo de procesamiento de cada elemento de la secuencia en los algoritmos de transmisión. A menudo, el procesamiento de datos solo es posible en una pasada.

Las restricciones estrictas de tiempo y memoria a menudo hacen que sea imposible resolver exactamente el problema en estudio. Los algoritmos de flujo suelen ser probabilísticos y dan una aproximación a la respuesta exacta.

Historia

Aunque tales algoritmos se consideraron en los trabajos de la primera mitad de la década de 1980 [1] [2] , el concepto de un algoritmo de transmisión se formalizó por primera vez en el trabajo de Alon , Matias ( ing. Yossi Matias ) y Szegedi ( ing. Mario Szegedy ) en 1996 [3] . En 2005, los autores recibieron el Premio Gödel por su contribución fundamental a los algoritmos de transmisión .

En 2005, se introdujo el concepto de un algoritmo de semitransmisión [ 4 ] como algoritmos que procesan el flujo entrante de forma constante o logarítmica .[ aclarar ] número de pases.

Modelo

En el modelo de flujo de datos, se considera que parte o la totalidad del conjunto de datos de entrada que deben procesarse no está disponible para el acceso aleatorio : los datos de entrada llegan de forma secuencial y continua en uno o más flujos. Los flujos de datos se pueden representar mediante una secuencia ordenada de puntos ("actualizaciones"), a los que se puede acceder en orden y solo una vez o un número limitado de veces.

Muchas publicaciones de subprocesos consideran la tarea de las estadísticas informáticas sobre una distribución de datos que es demasiado grande para un almacenamiento eficiente.[ especificar ] . Para esta clase de problemas, se supone que el vector (inicializado en cero ) tiene una cierta cantidad de "actualizaciones" en el hilo. El objetivo de tales algoritmos es calcular funciones utilizando significativamente menos espacio del que requeriría una representación completa del vector . Existen dos modelos generales para actualizar dichos datos: " caja registradora " y "torniquete" ( ing . torniquete ). $\mathbf {a} =(a_{1},\dots,a_{n})$ $\mathbf {0}$ ${\ matemáticas {a}}$ ${\ matemáticas {a}}$

En el modelo "cash", cada "actualización" se representa en el formulario y se modifica el vector de tal manera que aumenta en algún número entero positivo . Un caso especial es el caso (solo se permite insertar una unidad). ${\ estilo de visualización \ langle yo, c \ rangle}$ $ai}$ $C$ ${\ estilo de visualización c = 1}$

En el modelo "torniquete", cada "actualización" se representa en el formulario y se modifica el vector de tal manera que aumenta en algún número entero positivo o negativo . En un modelo estricto, en un momento dado no puede ser negativo. ${\ estilo de visualización \ langle yo, c \ rangle}$ $ai}$ $C$ $ai}$

En varias fuentes, también se considera el modelo de "ventana deslizante". En este modelo, la función de interés se calcula sobre una ventana de dimensionalidad limitada a partir de los datos del flujo, los elementos del final de la ventana no se tienen en cuenta hasta que los nuevos datos del flujo ocupan su lugar.

Estos algoritmos consideran no solo cuestiones relacionadas con las características de frecuencia de los datos, sino también una serie de otras. Muchos problemas de gráficos se resuelven bajo las condiciones de que la matriz de adyacencia del gráfico se cargue de antemano en un orden desconocido. A veces, por el contrario, es necesario resolver el problema de estimar el orden de los datos, por ejemplo, para contar el número de valores inversos en el flujo y encontrar la secuencia creciente más grande.

Comparación de algoritmos

Las principales características de los algoritmos de transmisión:

el número de pasadas permitidas del algoritmo sobre los datos;
memoria disponible;
tiempo de procesamiento[ especificar ] .

Estos algoritmos tienen mucho en común con los algoritmos en línea , ya que el algoritmo debe tomar una decisión antes de que todos los datos estén disponibles, pero existen diferencias. En particular, los algoritmos en línea tienen la capacidad de retrasar la toma de decisiones hasta que llega un grupo de puntos en una secuencia de datos, mientras que los algoritmos en línea deben tomar decisiones a medida que llega cada nuevo punto en una secuencia.

Si el algoritmo es aproximado, la precisión de la respuesta es otro indicador. La precisión de un algoritmo a menudo se representa como un valor , lo que significa que el algoritmo logrará menos errores con una probabilidad de . ${\ estilo de visualización (\ épsilon, \ delta)}$ $\epsilon$ ${\ estilo de visualización 1-\ delta}$

Aplicación

Los algoritmos de flujo son de gran importancia en las tareas de monitoreo y administración de redes informáticas, por ejemplo, por medio de ellos es posible prevenir rápidamente desbordamientos (seguimiento de flujos gigantes estimación del número y duración esperada de los desbordamientos) [ ] Además, los algoritmos de transmisión se pueden usar en bases de datos, por ejemplo, para estimar el tamaño después de una operación de unión de tablas .

Ejemplos de problemas resueltos por algoritmos de transmisión

Problemas con la distribución de frecuencias

$k$ El momento de frecuencia en el vector se define como . ${\ matemáticas {a}}$ ${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k))$

El primer momento es la simple suma de las frecuencias (es decir, el número total). El segundo punto es útil para calcular parámetros estadísticos de los datos, como el coeficiente de Gini . definida como la frecuencia del elemento que ocurre con mayor frecuencia. $F_{1}$ $F_{2}$ ${\ Displaystyle F_ {\ infinito}}$

También se estudian las cuestiones de estimación de momentos de frecuencia.

Búsqueda de elementos pesados

La tarea es encontrar el elemento que ocurre con más frecuencia en el flujo de datos. Aquí se aplican los siguientes algoritmos:

Algoritmo de voto mayoritario de Boyer-Moore
Algoritmo de Karp-Papadimitriou-Schenker ,
Bosquejo Count-Min ,
algoritmo de muestreo pegajoso , _
Algoritmo de recuento
"sample and hold" ( ing. sample and hold ),
filtro de floración en capas ,
contando "sketch" ( ing. Count-sketch ),
muestreo basado en "esquema" ing. muestreo guiado por croquis ,

Seguimiento de tendencias

La tendencia en un flujo de datos generalmente se realiza en el siguiente orden: los elementos más frecuentes y sus frecuencias se determinan en función de uno de los algoritmos anteriores.[ aclarar ] <--¿algoritmos para encontrar elementos pesados? y si esta sección se mueve hacia abajo?-->, y luego el mayor aumento en relación con el punto anterior en el tiempo se observa como una tendencia. Para ello se utiliza una media móvil exponencial y varias normalizaciones [6] . Utiliza el espacio O(ε² + log d) y la actualización del peor de los casos O(1) para una función hash universal de la familia de funciones hash independientes de r-smart con r = Ω(log(1/ε)/log log(1 / ε))[ especificar ] .

Entropía

Una estimación de entropía empírica sobre un conjunto de frecuencias se define como , donde [7] . ${\ matemáticas {a}}$ $F_{k}(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {\frac {a_{i} }{metro}}$ ${\displaystyle m=\sum _{i=1}^{n}a_{i))$

Aprendizaje automático

La tarea principal del aprendizaje automático en línea es entrenar un modelo (por ejemplo, un clasificador) en un solo paso a través del conjunto de entrenamiento; El hashing predictivo y el gradiente para

Contando el número de elementos únicos

Contar el número de elementos únicos en el flujo de datos (momento ) es otra $F_{0}$ [ aclarar ] un problema bien estudiado. El primer algoritmo fue propuesto por Flajolet y Martin [2] . En 2010, se encontró un algoritmo asintóticamente óptimo [8] .

Notas

↑ Munro y Paterson (1980 )
↑ 1 2 Flajolet y Martín (1985 )
↑ Alon, Matías y Szegedy (1996 )
↑ Feigenbaum Joan , Kannan Sampath , McGregor Andrew , Suri Siddharth , Zhang Jian. Sobre problemas de grafos en un modelo semi-streaming // Informática Teórica. - 2005. - diciembre ( vol. 348 , n. 2-3 ). - S. 207-216 . — ISSN 0304-3975 . -doi : 10.1016/ j.tcs.2005.09.013 .
↑ J. Xu Un tutorial sobre transmisión de datos de red
↑ Schubert Erich , Weiler Michael , Kriegel Hans-Peter. SigniTrend // Actas de la 20.ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos - KDD '14. - 2014. - ISBN 9781450329569 . -doi : 10.1145/ 2623330.2623740 .
↑ Las estimaciones de entropía fueron proporcionadas por McGregor et al., Do Ba et al., Lall et al., Chakrabarti et al.[ aclarar ]
↑ Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010), "Un algoritmo óptimo para el problema de elementos distintos", Actas del vigésimo noveno simposio ACM SIGMOD-SIGACT-SIGART sobre Principios de los sistemas de bases de datos, PODS '10, Nueva York, NY, EE. UU.: ACM, págs. 41-52, doi:10.1145/1807085.1807094, ISBN 978-1-4503-0033-9 .

Literatura

Alón, Noga ; Matias, Yossi & Szegedy, Mario (1999), La complejidad espacial de la aproximación de los momentos de frecuencia , Journal of Computer and System Sciences vol.58 (1): 137–147, ISSN 0022-0000 , DOI 10.1006/jcss.1997.1545 . Publicado por primera vez como Alon, Noga; Matias, Yossi & Szegedy, Mario (1996), La complejidad espacial de aproximar los momentos de frecuencia , Actas del 28º Simposio ACM sobre Teoría de la Computación (STOC 1996) , p. 20–29, ISBN 0-89791-785-5 , DOI 10.1145/237814.237823 .
Babcock, Brian; Babu, Shivnath; Datar, Mayur & Motwani, Rajeev (2002), Modelos y problemas en los sistemas de flujo de datos , Actas del 21° Simposio ACM SIGMOD-SIGACT-SIGART sobre los principios de los sistemas de bases de datos (PODS 2002) , pág. 1–16, doi : 10.1145/543613.543615 , < http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf > .
Gilberto, AC ; Kotidis, Y.; Muthukrishnan, S. & Strauss, MJ (2001), Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries , Actas de la Conferencia Internacional sobre Bases de Datos Muy Grandes : 79–88 , < http://www.vldb. org/conf/2001/P079.pdf > .
Kane, Daniel M.; Nelson, Jelani & Woodruff, David P. (2010), Un algoritmo óptimo para el problema de elementos distintos , PODS '10, Nueva York, NY, EE. UU.: ACM, p. 41-52, ISBN 978-1-4503-0033-9 , DOI 10.1145/1807085.1807094 .
Karp, R.M .; Papadimitriou, CH & Shenker, S. (2003), Un algoritmo simple para encontrar elementos frecuentes en flujos y bolsas , ACM Transactions on Database Systems Vol. 28 (1): 51–55 , DOI 10.1145/762471.762473 .
Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori y Xu, junio (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) , doi : 10.1145/1140277.1140295 , < ftp:/ /ftp.cs.rochester.edu/pub/papers/theory/05.tr886.Data_streamg_algms_for_estimating_entropy_of_network_traffic.pdf > (enlace inactivo) .
Xu, Jun (Jim) (2007), Tutorial sobre transmisión de datos de red , < http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf > .

Enlaces

Notas de la conferencia de Princeton
Algoritmos de transmisión para problemas geométricos , por Piotr Indyk , MIT
Taller Dagstuhl sobre algoritmos sublineales
Taller IIT Kanpur sobre transmisión de datos
Lista de problemas abiertos en la transmisión (compilada por Andrew McGregor ) de la discusión en el Taller IITK sobre algoritmos para flujos de datos, 2006.
StreamIt: lenguaje de programación e infraestructura de compilación de MIT CSAIL (enlace no disponible)
IBM Spade: motor declarativo de aplicaciones de procesamiento de flujo
Secuencias de IBM InfoSphere

libros de texto

Aplicaciones y algoritmos de flujo de datos por S. Muthu Muthukrishnan
Encuesta del proyecto Stanford STREAM
Aplicaciones de red de los filtros Bloom , por Broder y Mitzenmacher
Tutorial SIGMETRICS 2007 de Xu
Notas de clase del curso Data Streams en Barbados en 2009 , por Andrew McGregor y S. Muthu Muthukrishnan

Cursos