Voir le résumé
Une jointure floue est l'une des opérations de traitement et d'analyse de données les plus utiles pour le Big Data dans un contexte général. Il combine des paires de tuples dont la distance est inférieure ou égale à un seuil donné. La jointure floue est utilisée dans de nombreuses applications pratiques, mais elle est extrêmement coûteuse en temps et en espace, et peut même ne pas être exécutée sur des ensembles de données à grande échelle. Bien qu'il y ait eu quelques études pour améliorer ses performances en appliquant des filtres, une solution d'un filtre flou efficace pour la jointure floue n'a jamais été réalisée. Dans cette thèse, nous nous concentrons donc sur l'optimisation des grandes jointures floues à l'aide de filtres. Pour atteindre ces objectifs, nous appliquons d'abord des filtres Bloom aux opérations de grande jointure floue afin d'éliminer la plupart des éléments non joints dans les ensembles de données d'entrée avant d'envoyer les données au traitement de jointure réel. Ainsi, il réduit les données intermédiaires redondantes, les comparaisons inutiles et évite la duplication des données. Une autre proposition importante est les filtres flous, qui sont des structures de données probabilistes conçues pour représenter des ensembles et leurs éléments de similarité. Ils sont utilisés pour détecter rapidement les éléments proches de l'ensemble dans des seuils donnés avec un faible taux de faux positifs et zéro taux de faux négatifs. De plus, ces filtres sont non seulement indépendants avec des seuils et des fonctions de mesure de distance, mais aussi facilement mis à jour. Par conséquent, il peut être appliqué à un large éventail de problèmes courants tels que la déduplication, la correction d'erreurs, le nettoyage des données, l'intégration de données, les jointures récursives et les jointures de flux. Notre amélioration réduira considérablement le nombre de calculs redondants et les frais généraux associés tels que les données intermédiaires et la communication pour les opérations de déduplication. Nous effectuons ensuite des comparaisons d'analyse des algorithmes de jointure floue convaincantes sur la base d'un modèle de coût M-C-R. En conséquence, en utilisant les filtres proposés, les opérations de jointure floue peuvent minimiser les coûts d'E/S disque et de communication. De plus, les opérations de jointure floue basées sur des filtres se sont avérées plus efficaces que les solutions existantes grâce à des évaluations expérimentales dans Spark. Des comparaisons expérimentales de différents algorithmes pour les jointures floues sont examinées en ce qui concerne la quantité de données intermédiaires, la quantité totale de sortie, le temps total d'exécution et en particulier les calendriers des tâches. Bref, nos améliorations sur les opérations de jointure contribuent à la scène mondiale d'optimisation de la gestion des données pour les applications MapReduce sur des infrastructures distribuées à grande échelle.