Proposition De Nouveaux Mécanismes D’indexation Et De Compression Pour La Recherche D’information

Résumé: Les systèmes de recherche d’information actuels sont très volumineux et gèrent de grandes masses de données. À chaque fois, ils traitent des millions de documents et évaluent des milliers de requêtes par minute. Dans les moteurs de recherche, la réalisation des index passe par le calcul de l'intersection entre les documents alors que l'évaluation des requêtes est le fruit de l'intersection entre ces requêtes et les index. Ce problème de calcul de l'intersection entre des ensembles triés a suscité beaucoup d'intention depuis 1971, date d'apparition du premier algorithme. L'optimisation du nombre de comparaisons et des temps de calcul est le principal objectif que les algorithmes doivent atteindre. Ces algorithmes utilisent des structures de données efficaces et des méthodes ingénieuses. Récemment, de nombreuses recherches ont utilisé des techniques sur les cartes graphiques GPU (pour Graphics Processing Unit) pour résoudre le calcul de l'intersection entre les listes. La majorité de ces techniques se concentrent sur l'amélioration du niveau de parallélisme en réduisant les comparaisons redondantes et en distribuant la charge de travail de manière égale entre les threads du GPU. Dans cette thèse, nous présentons un nouvel algorithme de type diviser-pour-régner pour le calcul de l'intersection entre des listes ordonnées. Nous proposons l'algorithme GPU Test With Jumps (GTWJ) pour calculer l'intersection entre les listes triées en utilisant une nouvelle structure de données. L'idée de GTWJ est de regrouper les données de chaque liste triée en un ensemble de séquences. Une séquence est identifiée par une clé. L'intersection est calculée entre les séquences ayant la même clé. Cette clé permet de sauter des paquets de données en parallèle si les clés ne correspondent pas. Les expérimentations menées montrent que notre solution est performante.

Publié dans la revue: