Qué hay detrás de los trending topics? - Algoritmos de flujo

Dentro de las redes sociales, con millones de mensajes y eventos que se disparan, tener una idea global de los que está pasando en un determinado instante a veces no es un tema sencillo.
Por ejemplo conocer cuales son los hashtags más utilizados en Twitter en un determinado momento requiere - en una aproximación tradicional - mantener un registro de la cantidad de veces que se utilizó cada uno de ellos. A nivel de una red social como la del pajarito esto puede involucrar el procesamiento de millones de tags donde la mayoría no pasa la decena de menciones. Ese procesamiento requiere tiempo y espacio. La inmediatez en ese escenario no es posible, el tiempo de ingreso constante de nueva información convierte el proceso en un embudo que acumulando registros sin procesar con el tiempo. Para poder realizar este tipo de procedimientos se requiere otros tipo de métodos: Los algoritmos de flujo.

Embotellamiento frente a cabinas de peaje

Se conoce como "data stream" o fllujo de datos a una secuencia de elementos de tal magnitud que su almacenamiento en memoria es privativo. Su manipulación y proceso debe realizarse con cuidado puesto que hacer más de una iteración sobre los mismos suele estar fuera de posibilidad dado que terminan construyendo un cuello de botella de nuevos datos que van llegando provocando con el tiempo un desfasaje tal que los datos ya procesados terminan siendo inutiles por su antiguedad.

Un ejemplo conceptualmente afín es la circulación de autos en una autopista. El agregado de una cabina de peaje en el camino para procesar cada auto, si no es lo suficientemente ágil provocará un congestionamiento y si no es atendido a tiempo un retraso en la circulacion con el tiempo generará largas colas (y un sistema colapsado).

Los algorimos de flujo de datos son utilizados para obtener inormación estadística y el descubrimiento de información sobre los flujos de datos. Alguna de la información que se puede obtener es trivial, por ejemplo la cantidad total de elementos (en nuestro ejemplo la cantidad total de autos). En ese caso se tiene que tener un contador que a medida que se suceden los elementos se va incrementando. Incluso se puede calcular de forma eficiente la cantidad de elementos de un tipo determinado si la diversidad de elementos es acotada (en el caso de nuestra autopista podriamos decir la cantidad total de ruedas por auto simplemente por que la cantidad de posibilidades es limitada. llevando un contador por configuración y luego promediando.

Aproximación mediante muestreo

Existen otros tipo de problemas que no se pueden resolver directamente. Determinar la cantidad total de elementos diferentes que fueron sucediendose no es fácil si la cantidad de elementos distintos no esta acotado. Por ejemplo cuantos usuarios diferentes escribieron en un servicio de mensajeria en un determinado lapso de tiempo, cuantos posts diferentes se consultaron en una red social o los términos más buscados en un buscador en un determinado momento son ejemplos de este tipo. Para este tipo de problemas generalmente se intenta llegar a aproximaciones.

Para lograr aproximaciones varios algoritmos de flujo trabajan realizando un muestreo estadístico. En forma aleatoria seleccionan un subconjunto de elementos del stream de forma de lograr un proceso reducido. Existen dos grandes ramas en estos métodos. El muestreo de tamaño proporcional al stream y el muestreo de tamaño fijo.

El muestreo proporcional selecciona aleatoriamente un conjunto de elementos del stream. A cada elemento se le computa una propabilidad de selección y se selecciona o no de acuerdo a este valor. La cantidad de elementos seleccionados crece proporcionalmente a la cota de probabilidad a medida que los elementos se van sucediendo en el flujo. Habitualmente  se define una tasa de selección de tal manera que el procesamiento del la muestra pase a ser manejable en memoria o que permita realizar un procesamiento intensivo. Por ejemplo, para determinar que usuarios son los que más páginas visitan de un sitio se podría seleccionar la centésima (o milesima) parte de las visitas recibidas y luego procesar el lote obtenido. Al ser una selección al azar se puede considerar que las características de la parte separada son similares a las del stream original. Se debe tener en cuenta que si los eventos son muy dispersos y no existen elementos que son marcadamente diferentes en su repetición que otros este método sera muy dependiente del azar. Es no determinístico y por lo tanto los resultados al ejecutarse varias veces pueden ser diferentes. (Cabe aclarar que dado a la naturaleza del problema, volumen de datos y velocidad de actualización, realizar el proceso más de una vez no es una opción).
Una cuestión a tener en cuenta es que de acuerdo a la consulta a responder se deberá proceder diferente con la selección de los elementos Por ejemplo si se quiere conocer la cantidad promedio de comentarios que hacen los usuarios en un sitio, seleccionar al azar simplemente sobre todos los datos hará que el resultado sea senciblemente inferior al real. En este caso lo que se debe hacer es seleccionar una cantidad al azar de los usuarios y quedarse con los elementos de ellos. Por ejemplo seleccionar un 10% de los usuarios.

El muestreo de tamaño fijo intenta mantener limitado a un número acotado de muestras y que las mismas representen el universo total de los elementos en el stream vistos hasta el momento. Por ejemplo, sin importar el tamaño de flujo quedarse con 1000 elementos. Existen diversos algoritmos que siguen este lineamiento, la mayoria especializados en resolver diferentes tipos de problemas. Por ejemplo, el que da origen a esta nota, determinar aquellos temas de los que más se está hablando en un determinado momento. Para esto se puede utilizar el algoritmo de Misra-Gries propuesto en 1982. Para ello se mantienen en memoria una cantidad de celdas limitada en número (por ejemplo 100) cada una de ellas formadas por un identificador de elemento y un contador inicialmente en 0. Por cada elemento que llega se busca si está en alguna de las celdas. Si NO está y hay alguna celda vacia (con contador en cero) se la inserta con el contador en 1 en ella. Si, por el contrario está en alguna celda, se incrementa el contador de ella en 1. El último caso posible es que el elemento no esté y que no haya celdas vacias. En ese caso el elemento no se inserta y lo que se hace es decrementar en 1 todos los elementos de las celdas, descartando los que quedan en 0.
Aquellos elementos que en un determinado momento son repetidos varias veces tenderán a tener un número alto en el contador y a medida que dejan de presentarse irán bajando su valor haciendo que otros puedan tomar su lugar. En cada instante se pueden ver aquellos elementos que tienen el contador con el valor más elevado y corresponde a aquellos que son los más repetidos en ese lapso de tiempo.