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.