Algorithme de fouille de flots de données

En informatique théorique, un algorithme de fouille de flots de données, ou algorithme de streaming de streaming algorithm en anglais, est un algorithme prenant en entrée un flot continu d'items. Ces algorithmes ont en général peu de mémoire à leur disposition (beaucoup moins que la taille du volume en entrée) et peu de temps à accorder à chaque item. Ces contraintes peuvent impliquer qu'un tel algorithme fournit une réponse approchée fondée sur l'exploitation d'un résumé () du flot de données en mémoire. Le modèle partage certains aspects avec les algorithmes onlines, mais les deux modèles sont différents. Dans un algorithmes de streaming la réponse peut être donnée de façon différée, et la difficulté est le peu d'espace disponible, il peut même y avoir plusieurs passes sur la donnée. Au contraire pour les algorithme online, les décisions doivent être prises au fur et à mesure de la réception des informations, et les ressources en espace et en temps de calcul ne sont pas limitées. Pour la recherche d'items fréquents dans un flot de données, il y a deux types d'algorithmes : les algorithmes fondés sur les comptages et les algorithmes axés sur les résumés (). Sticky Sampling et Lossy-Counting sont deux algorithmes importants dans ce domaine ne serait-ce que parce qu'ils sont des références. Ce sont tous les deux des algorithmes orientés faux-positifs () à savoir, ils s'autorisent à présenter en résultat des items ou des itemsets fréquents alors qu'ils ne le sont pas, mais aucun faux-négatifs sont oubliés. Lossy-Counting est un des premiers algorithmes d'exploration des flots de données utilisant le modèle des fenêtres à drapeau (). C'est un algorithme paramétrique qui accepte deux paramètres de l'utilisateur : et où est le taux d'erreur et s le seuil de support souhaités par l'analyste. Si N est le nombre d'items (itemsets) venant d'arriver, l'algorithme utilise des fenêtres de longueur 1/.