Algorithme de Flajolet et Martin

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).

L'algorithme

modifier

L'algorithme nécessite une fonction de hashage , associant à une entrée  un entier dans , dont les images sont uniformément réparties. L'ensemble des entiers de 0 à correspond en fait à l'ensemble des chaînes binaires de longueur .

Étant donné un entier positif , on note  le -ème bit dans la représentation binaire de , de sorte que :

On définit ensuite une fonction  qui associe à y la position du bit de poids faible dans sa représentation binaire :

avec . Par exemple, car le premier bit est non nul, alors que  avec le bit de poids faible en troisième position. Étant donné que les images de la fonction de hashage sont uniformément réparties, la probabilité d'observer un nombre finissant par  (un 1 suivi de  zéros) est  et correspond à tirer  piles suivi d'un face en lançant une pièce de monnaie équilibrée.

Description de l'algorithme

modifier

Algorithme de Flajolet-Martin — L'algorithme de Flajolet–Martin estime la cardinalité d'un multiensemble  de la manière suivante :

  1. Initialiser un vecteur BITMAP contenant  zéros.
  2. Pour chaque élément  dans , effectuer :
    1. ,
    2. .
  3. On note  le plus petit indice  tel que .
  4. La cardinalité de  est approchée par  avec .

Commentaires

modifier

Avec  le nombre d'éléments distincts de , alors  est accédé environ  fois, accédé  fois, etc. Ainsi, si  vaut certainement 0, de même que si  vaut certainement 1. Si  alors  vaut soit 1 soit 0.

Les calculs pour obtenir le facteur de correction  sont détaillés dans l'article de Flajolet et Martin.

Voir aussi

modifier

Références

modifier
  1. Référence pour le nom : Claire Mathieu, « Support du cours « Algorithmes pour flux de données » au collège de France, le 16 janvier 2018 », sur Collège de France.
  2. Philippe Flajolet et G. Nigel Martin, « Probabilistic counting algorithms for data base applications », Journal of Computer and System Sciences, vol. 31, no 2,‎ , p. 182–209 (DOI 10.1016/0022-0000(85)90041-8, lire en ligne)
  3. (en) Marianne Durand et Philippe Flajolet, Algorithms - ESA 2003 : 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings, vol. 2832, coll. « Lecture Notes in Computer Science », , 605 p. (ISBN 978-3-540-20064-2, DOI 10.1007/978-3-540-39658-1_55, lire en ligne), « Loglog Counting of Large Cardinalities »
  4. Philippe Flajolet, Éric Fusy, Olivier Gandouet et Frédéric Meunier, « Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm », Discrete Mathematics and Theoretical Computer Science,‎ , p. 127–146 (lire en ligne)
  5. (en) D. M. Kane, J. Nelson et D. P. Woodruff, Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems of data - PODS '10, (ISBN 978-1-4503-0033-9, DOI 10.1145/1807085.1807094, lire en ligne), « An optimal algorithm for the distinct elements problem », p. 41

Liens externes

modifier