Estimation du nombre d'éléments distincts de grands ensembles

Frédéric Giroire
Projet Algo, INRIA Rocquencourt


Résumé:

Le probleme considere ici est d'estimer le nombre d'elements distincts n, ou cardinalite, de tres grands multi-ensembles de taille N. Les algorithmes de comptage exact utilisent une memoire en O(n) et ont un temps d'execution en O(N log n). Or notre motivation pour ce probleme vient de l'analyse de tres grandes bases de donnees ou du traffic internet. Dans ces domaines le volume gigantesque des donnees considerees rend impossible l'emploi d'algorithmes avec une memoire lineaire. Les liens des reseaux internet ``backbone'', comme OC-192 des reseaux SONET, peuvent avoir une capacite de 10 Gbps. Les seuls algorithmes qui peuvent etre utilies doivent avoir une memoire constante et ne faire qu'une passe sur les donnees. L'idee principale est de transformer le probleme en un probleme probabiliste. Il ne s'agit plus de chercher le nombre exact de mots distincts, mais une estimee de ce nombre avec une precision donnee. On introduit ici plusieurs classes d'algorithmes pour repondre a ce probleme. Elles atteignent une erreur standard de 1/sqrt M en utilisant M unites de memoire.

Retour au séminaire