Maintenir des statistiques de flux sur des fenêtres glissantes : (résumé étendu)

Mayur Datar Aristides Gionis et Piotr Indyk et Rajeev Motwani x Résumé Nous considérons le problème de maintenir des agrégats et des statistiques sur des flux de données, en ce qui concerne les N derniers éléments de données vus jusqu'à présent. Nous appelons ce modèle le modèle de fenêtre glissante. Nous considérons le problème de base suivant : Étant donné un flux de bits, maintenir un compte du nombre de 1 dans les N derniers éléments vus du flux. Nous montrons qu'en utilisant O(1 ε log 2 N) bits de mémoire, nous pouvons estimer le nombre de 1 à un facteur près de 1 + ε. Nous donnons également une borne inférieure correspondante de \ 1 ε log 2 N) bits de mémoire pour tout algorithme déterministe ou aléatoire. Nous étendons notre schéma pour maintenir la somme des N derniers entiers positifs. Nous fournissons des bornes supérieures et inférieures correspondantes pour ce problème plus général également. Nous appliquons nos techniques pour obtenir des algorithmes efficaces pour les normes Lp (pour p 2 1 ; 2) de vecteurs selon le modèle de fenêtre glissante. En utilisant l'algorithme pour le problème de comptage de base, on peut adapter de nombreuses autres techniques pour fonctionner avec le modèle de fenêtre glissante, avec une surcharge multiplicative de O(1 ε log N) en mémoire et une perte de précision de facteur 1 + ε. Cela inclut le maintien d'histogrammes approximatifs, de tables de hachage et de statistiques ou d'agrégats tels que la somme et les moyennes.