Flux de données : algorithmes et applications

Cette séance de cours introduit le concept de flux de données, en se concentrant sur le calcul de statistiques avec une mémoire sous-linéaire et en estimant efficacement les quantités. Il couvre des techniques telles que le comptage d'éléments distincts, la recherche de frappeurs lourds et l'approximation du nombre-distinct à l'aide d'algorithmes tels que Flajolet-Martin. La séance de cours explore également la similitude des documents, discutant des bardeaux, des croquis et des méthodes de comparaison des croquis. En outre, il explore les distances et les requêtes les plus proches des voisins dans des données de grande dimension, présentant des techniques de réduction de dimension randomisées telles que le lemme Johnson-Lindenstrauss et la projection aléatoire. L'instructeur fournit des exemples pratiques et des applications, soulignant l'importance de ces algorithmes dans la gestion des défis «Big Data».