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 ). 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 de 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 "boceto" del flujo de datos.
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] 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 transmisión". Desde entonces, ha habido una gran cantidad de trabajo centrado en los 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 semitransmisión se introdujeron en 2005 como una relajación de los algoritmos de transmisión 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 el espacio.
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 uno a la vez en un "flujo". [5] Si el flujo tiene una longitud n y el dominio tiene un tamaño m , los algoritmos generalmente se ven obligados a usar un espacio logarítmico en m y n . Por lo general, solo pueden hacer un pequeño número constante de pases sobre la corriente, a veces solo uno . [6]
Gran parte de la literatura de transmisión se ocupa de 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 en el vector cero ) que tiene actualizaciones presentadas en un flujo. 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]
