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 ). En la mayoría de los modelos, estos algoritmos tienen acceso a una memoria limitada (generalmente logarítmica en el tamaño y / o el valor máximo en la secuencia). También pueden tener un tiempo de procesamiento limitado por artículo.
Estas restricciones pueden significar que un algoritmo produce una respuesta aproximada basada en un resumen o "bosquejo" del flujo de datos.
Historia
Aunque los algoritmos de transmisión 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 transmisión se formalizó y popularizó por primera vez en 1996. artículo de Noga Alon , Yossi Matias y Mario Szegedy . [3] Para este artículo, los autores luego ganaron 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 semiflujo se introdujeron en 2005 como una relajación de los algoritmos de flujo para gráficos, [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 gráficos densos y puede resolver problemas interesantes (como la conectividad) que son insolubles en espacio.
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 el flujo tiene una longitud n y el dominio tiene un tamaño m , algoritmos son generalmente limitados al espacio uso que es logarítmica en m y n . Por lo general, solo pueden hacer una pequeña cantidad constante de pasadas sobre el arroyo, a veces solo una . [6]
Modelos de torniquete y caja registradora
Gran parte de la literatura sobre transmisión se refiere a la computación de estadísticas sobre distribuciones de frecuencia que son demasiado grandes para ser almacenadas. Para esta clase de problemas, hay un vector (inicializado al vector cero ) que tiene actualizaciones presentadas en una secuencia. El objetivo de estos algoritmos es calcular funciones de utilizando considerablemente menos espacio del que se necesitaría para representar precisamente. Hay dos modelos comunes para actualizar dichos flujos, llamados modelos de "caja registradora" y "torniquete". [7]
En el modelo de caja registradora cada actualización es de la forma , así que eso se incrementa en algún número entero positivo . Un caso especial notable es cuando (solo se permiten inserciones de unidades).
En el modelo de torniquete cada actualización es de la forma , así que eso se incrementa en algún número entero (posiblemente negativo) . En el modelo de "torniquete estricto", no en cualquier momento puede ser menor que cero.
Modelo de ventana corredera
Varios artículos también consideran el modelo de "ventana deslizante". [ cita requerida ] En este modelo, la función de interés es calcular sobre 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 los 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 el entorno en el que la matriz de adyacencia o la lista de adyacencia del gráfico se transmite en un 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 requerida ]
Evaluación
El rendimiento de un algoritmo que opera en flujos de datos se mide por tres factores básicos:
- El número de pasadas que debe realizar el algoritmo en 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 tomar medidas tan pronto como llegue cada punto.
Si el algoritmo es un algoritmo de aproximación, la precisión de la respuesta es otro factor clave. La exactitud se expresa a menudo como un aproximación, lo que significa que el algoritmo logra un error de menos de con probabilidad .
Aplicaciones
Los algoritmos de transmisión tienen varias aplicaciones en redes , como monitorear enlaces de red para flujos de elefantes , 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 [ cita requerida ] .
Algunos problemas de transmisión
Momentos de frecuencia
El k- ésimo momento de frecuencia de un conjunto de frecuencias Se define como .
El primer momento es simplemente la suma de las frecuencias (es decir, el recuento total). El segundo momentoes ú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 artículos más frecuentes.
El artículo fundamental de Alon, Matias y Szegedy trató el problema de estimar 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 memoria de orden. [3] Pero tenemos limitaciones de espacio y requerimos un algoritmo que compute en una memoria mucho menor. 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]
Cálculo de F 0 (elementos distintos en un flujo de datos)
Algoritmo FM-Sketch
Flajolet y col. en [2] introdujo el método probabilístico de contar 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 y col. en [2] mejoró este método mediante el uso de una función hash h que se supone distribuye uniformemente el elemento en el espacio hash (una cadena binaria de longitud L ).
Deje que el bit ( y, k ) represente el k-ésimo bit en representación binaria de y
Dejar representa la posición de 1 bit menos significativo en la representación binaria de y i con una convención adecuada para.
Sea A la secuencia del flujo de datos de longitud M cuya cardinalidad necesita ser determinada. Sea BITMAP [0 ... L - 1] el
espacio hash donde se registran los ρ ( valores hash ). La continuación algoritmo determina entonces cardinalidad aproximado de A .
Procedimiento FM-Sketch: para i en 0 a L - 1 hacer BITMAP [i]: = 0 final para para x en A: haz Índice: = ρ (hash (x)) si BITMAP [índice] = 0 entonces BITMAP [índice]: = 1 terminara si final para B: = Posición del bit 0 más a la izquierda de BITMAP [] return 2 ^ B
Si hay N elementos distintos en un flujo de datos.
- Para entonces BITMAP [ i ] es ciertamente 0
- Para entonces BITMAP [ i ] es ciertamente 1
- Para entonces BITMAP [ i ] es una franja de 0 y 1
Algoritmo de valor mínimo K
El algoritmo anterior describe el primer intento de aproximar F 0 en el flujo de datos de Flajolet y Martin. Su algoritmo elige una función hash aleatoria que asumen distribuye uniformemente los valores hash en el espacio hash.
Bar-Yossef y col. en [10] introdujo el algoritmo de valor mínimo k para determinar el número de elementos distintos en el flujo de datos. Utilizaron una función hash similar h que se puede normalizar a [0,1] como. Pero fijaron un límite t al número de valores en el espacio hash. El valor de t se asume del orden(es decir, menos valor de aproximación ε requiere más t ). KMV algoritmo mantiene solamente t valores hash -smallest en el espacio de hash. Después de que hayan llegado todos los valores m de la secuencia, se usa para calcular. Es decir, en un espacio hash casi uniforme, esperan que al menos t elementos sean menores que.
Procedimiento 2 Valor mínimo de KInicializar los primeros valores t de KMV para un en a1 para hacersi h (a)Eliminar Max (KMV) del conjunto KMVInserte h (a) en KMV terminara sifinal para retorno t / Max (KMV)
Análisis de complejidad de KMV
El algoritmo KMV se puede implementar en espacio de bits de memoria. Cada valor hash requiere espacio de ordenbits de memoria. Hay valores hash del pedido.. El tiempo de acceso se puede reducir si almacenamos los valores de t hash en un árbol binario. Por lo tanto, la complejidad del tiempo se reducirá a.
Calculando F k
Alon y col. 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 .
Suponga que la longitud de la secuencia m se conoce de antemano. Luego construya una variable aleatoria X de la siguiente manera:
- Seleccione a p sea un miembro aleatorio de la secuencia A con índice en p ,
- Dejar , representa el número de apariciones de l dentro de los miembros de la secuencia A que sigue a p .
- Variable aleatoria .
Suponga que S 1 es del ordeny S 2 sea del orden. Algoritmo toma S 2 variable aleatoria Y 1 , Y 2 , ..., Y S 2 y salidas de la mediana de Y . Donde Y i es el promedio de X ij donde 1 ≤ j ≤ S 1 .
Ahora calcule la expectativa de la variable aleatoria E ( X ) .
Complejidad de F k
A partir del algoritmo para calcular F k discutido anteriormente, podemos ver que cada variable aleatoria X almacena el valor de a p y r . Por lo tanto, para calcular X tenemos que mantener únicamente log ( n ) bits para almacenar un p y log ( n ) bits para almacenar r . El número total de variable aleatoria X será el.
Por lo tanto, la complejidad espacial total que toma el algoritmo es del orden de
Enfoque más simple para calcular F 2
El algoritmo anterior calcula con el fin de bits de memoria. Alon y col. en [3] simplificó este algoritmo utilizando una variable aleatoria independiente de cuatro lados con valores asignados a.
Esto reduce aún más la complejidad para calcular a
Elementos frecuentes
En el modelo de flujo de datos, el problema de los elementos frecuentes es 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 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 del valor i en la corriente. El problema de los elementos frecuentes es generar el conjunto { i | f i > m / c}. [13]
Algunos algoritmos notables son:
- Algoritmo de voto mayoritario de Boyer-Moore
- Bosquejo de Count-Min
- Conteo con pérdidas
- Filtros Bloom de varias etapas
- Resumen de Misra – Gries
Detección de eventos
La detección de eventos en los flujos de datos a menudo se realiza utilizando un algoritmo de peso pesado como se enumera anteriormente: los elementos más frecuentes y su frecuencia se determinan utilizando uno de estos algoritmos, 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 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 el espacio O ( ε 2 + log d ) , con O (1) tiempos de informe y actualización 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 , dónde .
Aprender en línea
Aprenda un modelo (por ejemplo, un clasificador ) con una sola pasada sobre un conjunto de entrenamiento.
- Función hash
- 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. Con mucho, 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 ]
Ver también
- Minería de flujo de datos
- Agrupación de flujos de datos
- Algoritmo en línea
- Procesamiento de flujo
- Algoritmo secuencial
Notas
- ^ Munro, J. Ian; Paterson, Mike (1978). "Selección y clasificación con almacenamiento limitado". XIX Simposio anual sobre los fundamentos de la informática, Ann Arbor, Michigan, EE. UU., 16-18 de octubre de 1978 . Sociedad de Informática IEEE. págs. 253-258. doi : 10.1109 / SFCS.1978.32 .
- ↑ a b c Flajolet y Martin (1985)
- ↑ a b c d Alon, Matias y Szegedy (1996)
- ^ Feigenbaum, Joan; Sampath, Kannan (2005). "Sobre problemas de gráficos en un modelo de semi-transmisión" . Informática Teórica . 348 (2).
- ^ Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002). Modelos y problemas en los sistemas de flujo de datos . Actas del 21º 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. 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 en Ciencias de la Computación. 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.
- ^ 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 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 .
- ^ a b 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 en Ciencias de la Computación. 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.
- ↑ 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 EE. UU. págs. 1-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 significación hash . Actas de la 20a 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
- 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, S2CID 1627911.
- Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev ; Widom, Jennifer (2002), "Modelos y problemas en los 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.
- 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 elementos distintos , 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 Parámetro desconocido
|book-title=
ignorado ( ayuda ) . - 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) (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", Proceeding IJCAI'91 Proceedings of the 12th international joint conference on Artificial intelligence - Volume 2, páginas 777-782, Morgan Kaufmann Publishers Inc. San Francisco, CA, EE. UU. © 1991
- Morris, Robert (1978), "Contando un gran número de eventos en pequeños registros", Comunicaciones del ACM , 21 (10): 840–842, doi : 10.1145 / 359619.359627 , S2CID 36226357.