RNTI

MODULAD
Calcul de l'intersection entre listes triées à base de sauts
In EDA 2018, vol. RNTI-B-14, pp.57-72
Résumé
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. Dans ce contexte, nous présentons un nouvel algorithme de type diviser-pour-régner pour le calcul de l'intersection entre des listes ordonnées. Le prétraitement sur les listes est présenté en détail. Il permet à notre algorithme d'éviter de comparer des parties qui ne seront pas forcément partagées par ces listes. Les expérimentations menées montrent que notre solution est performante.