¿Qué herramientas, algoritmos o estructuras de datos usaría para construir un algoritmo de “Temas de tendencias” para una transmisión de alta velocidad?

Está buscando el artículo titulado Encontrar elementos frecuentes en flujos de datos escritos por Moses Charikar, Kevin Chen y Martin Farach-Colton

Puede buscar ese título en Google Scholar. Aquí hay un extracto:

Abstracto. Presentamos un algoritmo de 1 paso para estimar los elementos más frecuentes en un flujo de datos utilizando un espacio de almacenamiento muy limitado. Nuestro método se basa en una nueva estructura de datos llamada boceto de conteo, que nos permite estimar las frecuencias de todos los elementos en la secuencia. Nuestro algoritmo logra mejores límites de espacio que los algoritmos más conocidos anteriores para este problema para muchas distribuciones naturales en las frecuencias de los elementos. Además, nuestro algoritmo conduce directamente a un algoritmo de 2 pasadas para el problema de estimar los elementos con el mayor cambio (absoluto) de frecuencia entre dos flujos de datos. Hasta donde sabemos, este problema no ha sido estudiado previamente en la literatura.

…

Dado un flujo de datos q1, …, qn, para cada j = 1, …, n:

Agregar (C, qj) 2. Si qj está en el montón, incremente su recuento. De lo contrario, agregue qj al montón si Estimate (C, qj) es mayor que el recuento estimado más pequeño en el montón. En este caso, el recuento estimado más pequeño debe ser desalojado del montón.

He usado el algoritmo de clasificación de Hacker News en el pasado, y funciona muy bien. También es uno de los más fáciles de implementar. Se ve así en SQL cuando se usa con Postgres:

  Mensaje de clase
   alcance: clasificado,: select => "*, 
 (like_count + comment_count) / POW (((round (date_part ('epoch', 
 (NOW ()))) - round (date_part ('epoch', (created_time)))) / 3600) + 8, 8.0) 
 AS rank ",: order =>" rank DESC " 
 fin