Mantenimiento de la varianza y k-medians sobre ventanas de flujo de datos

El modelo de ventana deslizante es útil para descartar datos obsoletos en aplicaciones de flujo de datos. En este modelo, los elementos de datos llegan continuamente y solo los N elementos más recientes se utilizan al responder consultas. Presentamos una técnica novedosa para resolver dos problemas importantes y relacionados en el modelo de ventana deslizante: mantener la varianza y mantener un agrupamiento k-median. Nuestra solución al problema de mantener la varianza ofrece una estimación continuamente actualizada de la varianza de los últimos N valores en un flujo de datos con un error relativo de como máximo #, utilizando O(# 2 log N) memoria. Presentamos un algoritmo de aproximación de factor constante que mantiene una solución aproximada de k-median para los últimos N puntos de datos utilizando O(N) memoria, donde # 1/2 es un parámetro que intercambia el límite de espacio con el factor de aproximación de O(2).