On souhaite compter le nombre de flots transitant par un routeur du web. Le débit est tel qu'il est impossible de garder en mémoire tous les flots qui passent, ni d'effectuer beaucoup de calculs. La théorie de l'information semble indiquer qu'une telle tâche est impossible. Mais qu'en est-il si l'on ne souhaite qu'estimer ce nombre ? Ce type de questions se retrouve dans le contexte de la sécurité des réseaux puisque de nombreuses attaques se caractérisent par une augmentation inattendue du nombre de flots. L'algorithme probabiliste LogLog, proposé par Durand et Flajolet en 2003, répond à cette requête : en utilisant m registres de taille log(log(N)), il peut compter jusqu'à N éléments distincts, avec une erreur relative de l'ordre de 1.3/sqrt(m).
Récemment, en changeant d'estimateur, il a été possible de ramener l'erreur relative à 1.04/sqrt(m), ce qui fait actuellement de ce nouvel algorithme le meilleur et le plus simple effectuant cette tâche. Ce travail a été mené en commun avec Éric Fusy, Philippe Flajolet et Olivier Gandouet.
Les techniques utilisées pour analyser l'algorithme sont la transformée de Mellin, la poissonisation et la dépoissonisation analytique.