Algorithme de Flajolet et Martin
De Wikipedia, l'encyclopédie encyclopedia
Pour les articles homonymes, voir Flajolet.
L'algorithme de Flajolet et Martin[1] est un algorithme donnant une estimation du nombre d'éléments distincts dans un flot, en une seule passe et avec une complexité logarithmique en mémoire, proportionnelle au nombre maximum d'éléments distincts. Cet algorithme a été inventé en 1984 par Philippe Flajolet and G. Nigel Martin[2], puis amélioré par Marianne Durand et Philippe Flajolet[3],[4]. C'est un algorithme de fouille de flots de données (streaming).
En 2010[5], Daniel M. Kane, Jelani Nelson et David P. Woodruff ont proposé un algorithme avec une complexité spatiale presque optimale et un coût de modification en O(1).