Fathya Zemmouri

IFT6261

Université de Montréal

2

Plan présentation

� World-Wide-Web � Moteurs de recherche : Défis et justifications

� Architecture générique d’un moteur de recherche

� Évaluation des moteurs de recherche� Conclusion� Références

3

World-Wide-Web

Base de données : textes, images, audio, vidéos,…� Non structurée vs. Base de données relationnelle� Omniprésente� Géante : Téraoctets de données� Taille croissante continuellement� Change de contenu rapidement� Structure interliée : Hyperlink

4

WWWNœud de Papillon [2]

5

Étendu du Web

� Le 8 juillet 1999, MM. Steve Lawrence et C. Lee Giles annoncent que le web public a 800 millions de pages dans la revue Nature[5].

� Le 18 janvier 2000, Inktomi et NEC Research Institute publient une étude selon laquelle le web compterait 1 milliard de pages web [6].

� Le 11 juillet 2000, la société Cyveillance évalue à plus de 2 milliards de pages web. Pour suivre le développement du web, elle avait placé sur sa page d'accueil un compteur donnant au 1er janvier 2001 plus de 3 milliards de page [7].

6

Moteur de rechercheDéfis

� Données distribuées : multitude de plateformes, topologie anarchique de la toile

� Données dynamiques : changement ou disparition� Expansion du la toile : exponentielle� Données redondantes (syntaxe et sémantique) et

non structurées� Mauvaise qualité de données : orthographe,

grammaire,…� Hétérogénéité de données : différents alphabets

(chinois, japonais, kanji, …)

7

Moteurs de RechercheHistorique

� 1990 -> Archie : indexer les sites anonymes FTP� 1993 -> Aliweb : moteur HTTP, ne parcourt pas le Web, les

auteurs envoient leurs fichiers� 1994 -> WWW Worm : 1er robot qui explore la toile, ne

conserve que le titre des pages� Fin 1994 -> Yahoo : sommaire du Web

Web Crawler : Scanne toute la pageAltavista & Lycos

Problème majeur : absence de pertinence dans le résultat� 1998 -> Google : résultat pertinent, interface sobre, vitesse

8

Moteurs de RechercheArchitecture générique [16]

Requêtes

Explorateur(s)

WWW

Control d’exploration

Module d’indexation

Analyse de collection

Classement(Ranking)

Moteur de requêtes

Index : Texte Structure Utilité

Client

Résultats

Dépôt de pages

Rétroaction de l’utilisation

9

Module Explorationcrawler

1- Des robots explorateurs (programmes) :� Explorent la toile� Alimentent le dépôt de pages Web2- Control d’exploration :� Quelles pages explorer ? Pages « importantes »� Avec quelle priorité ? Ordre de priorité� Avec quelle stratégie ? Méthodes d’explorations� Quelles pages rafraîchir ? Fréquence de

rafraîchissement

10

Module d’ExplorationSélection de pages à explorer

� Pages « importantes » d’abord -> Métriques d’importance :� Intérêt : IS(P) ou IS’(P) (similarity interest)

Similarité entre une page et une requête Q� Popularité : IB(P) ou IB’(P) (BackLink Interest)

Le nombre de liens pointant vers P� Localisation : IL(P) ou IL’(P) (Location Interest)

Distance entre les pages Web

11

Module d’ExplorationMétrique d’importance : intérêt

� P = (w1, w2,…wm) et Q = (w’1,w’2,…,w’m)� Fréquence inverse dans le document :

idf(« mot ») = log(Nombre de pages dans toute la toile / Nombre de pages contenant « mot »)exemple : « le » ou « the » ont un idf insignifiant

� Avec wi = 0 si le ième mot de l’alphabet n’apparaît pas dans le document, et

� wi = occurrence(i_mot) * idf(i_mot)

� IS(P) = P.Q -> la similarité textuelle entre P et Q

12

Module d’ExplorationMétriques d’ordre

� Sélection des URLs à explorer dans une queue par ordre de priorité suivant une métrique d’ordre :� Combinaison de plusieurs métriques d’importance :

IC(P) = k1.IS(P) + k2.IB(P) + k3.IL(P)ou IC’(P) : calcul sur les pages déjà explorées.

13

� Explorer et arrêter : Le robot explore K pages (P0, P1, …, Pk)

� Robot parfait : explore K pages avec importance décroissanteSont appelées Pages chaudes (hot pages)

� Robot réel : explore (m <= K) pages avec importance >= àcelle de Pk

� Performance(robot idéal) = 100 %� Performance(robot réel) = M.100/K

Module d’ExplorationStratégies

14

� Explorer et arrêter avec seuil d’importance G :� Page avec importance > G -> page chaude� Robot explore K pages et arrête� Si le nombre des pages chaudes est H et le nombre de pages totale est T alors :

� Performance(robot idéal) = (K.100)/H (100 % si k >= H)� Performance(robot aléatoire) = Nb pages chaudes explorées * 100 / H .Nb pages chaudes explorées = (H/T) * K

(H/T est la probabilité pour qu’une page explorée soit chaude)D’où :� Performance(robot aléatoire) = K*100 /T

Module ExplorationStratégies (suite)

15

Comparaison entre stratégies d’explorationSite de l’Université Stanford [16]

16

Module ExplorationRafraîchissement

� Évolution de la toile -> � pages Web obsolètes -> � rafraîchissement de pages déjà chargées ->� Mesurer la fraîcheur d’une page

� Métrique fraîcheur

F(p,t) = 1 si p est à jour à l’instant t et 0 sinonF(S,t) = (1/|S|)*somme(F(pi,t)) � Métrique âge

A(p,t) = 0 si p est à jour à l’instant t, et = t – l’instant de la dernière modification de p

A(S,t) = (1/|S|)*somme(A(pi,t))

17

Module ExplorationRafraîchissement (suite)

� Stratégies de rafraîchissement pour :� Maximiser la métrique fraîcheur, et� Minimiser la métrique âge

1- Uniforme : Rafraîchit toutes les pages de la même manière

Donne de bons résultats si la différence de fréquence de changement entre les pages est élevée

2- Proportionnelle : fréquence de rafraîchissement proportionnelle à la fréquence de changement

18

Module ExplorationRafraîchissement (suite) [16]

Changement de fréquence vs fréquence de rafraîchissement sur un scénario de 5 pages et un taux de changement variant ente 1 et 5 fois/jour

19

Moteurs de rechercheModule Stockage

� Stocke des collections de pages Web fournit par le module d’exploration

� Fournit deux composantes :� Une interface pour les robots d’exploration pour stocker les pages

chargées� Une API pour le module d’indexation et le module d’analyse de

collection pour la recherche des pages

� A besoin de requêtes simples � mais optimisées en vitesse et en espace -> Paralléliser les

calculs et le stockage� Résistant aux pannes ->stockage distribué sur plusieurs

machines -> fonction d’adressage de pages Web

20

Moteurs de rechercheModule Stockage [16]

Séparation de la mise à jour et de la lecture sur les nœuds du dépôt de pages

21

Moteurs de rechercheModule Indexation

� Permet au moteur de construire une structure de données afin d’accroître sa vitesse de réponse

� Construit un index de liens : le graphe inverse du graphe des hyper-liens :� structure qui associe à chaque mot la liste de ses

occurrences dans les pages explorées.Mot -> l’identifiant d’une page et l’occurrence du mot dans la

page

� Construit un lexique :Mot -> Des statistiques comme nombre d’occurrence,…

22

� La construction des listes d’occurrence d’une page se déroule en trois étapes :� Lecture de la page (utilisation du réseau),� Construction d’une liste d’occurrences pour chaque mot (utilisation du processeur et de la RAM)

� Sérialisation des listes construites (utilisation du disque).

� Requiert trois ressources indépendantes, � Ordonnancement

Moteurs de rechercheModule Indexation

23

24

Moteurs de RechercheModule Classement

� Classer le résultat de la recherche par pertinence de la page par rapport à la requête

� Affecter à chaque page un poids en utilisant :� Algorithmes de classement :

� HITS (Hypertext Induced Topic Search)� PageRank (créateurs de Google)� D’autres algorithmes secrets …

� Se basent sur les hyperliens plus que sur le contenu de la page (facilement manipulable)Hypothèse : Un lien dans une page signifie une recommandation

25

� L’idée : � Une page importante est celle possédant le plus de liens

entrants � Liens entrants doivent être à leur tour importants

exemple : une page pointée par Yahoo vs Une page pointée par un site obscur

� L’algorithme : R(i) ensemble de pages pointant vers i S(i) ensemble de pages pointées par i

PR(i) = somme (PR(j) / |S(j)|) avec j parcourant R(i)

Module ClassementPageRank

26

� Pour chaque requête deux scores sont calculés :� Score d’autorité� Score de concentrateur

� Une page qui fait autorité est pointée par beaucoup de concentrateur

� Une page qui joue le rôle de concentrateur pointe vers beaucoup de pages autoritairesExemple : Sites traitant des voitures

Les sites des constructeurs sont des autoritésLes sites des magasines automobiles sont des concentrateurs

� Le calcul de l’un des deux scores dépend de l’autre score� Le moteur affiche les pages qui ont le score d’autorité le plus

élevé.

Module ClassementHITS

27

� Problème de classement :des liens sont des retours vers le sommaired’autres sont des publicités

� Google utilise une centaine d’algorithmes pour le classement� Chercher les mots dans l’URL plutôt que dans le titre� Préférer les URLs courtes aux URLs longues� La police du mot trouvé dans la page : un titre est plus

important que le corps de la page

Module ClassementAnalyse des liens

28

Dérivés des Moteurs de recherche

� Cercle Web

regroupement de sites partageant le même thème, reliés par un système de navigation

Exemple : Meta Ring, Ring Surf, Web Ring� Méta Moteur de Recherche : distribue la requête

via plusieurs moteurs de rechercheExemple : Carmel, Beaucoup, All the Web, Kartoo� Portail : Moteur de recherche + des hyperliens vers

des sites d’actualités, d’informations…Exemple : Yahoo, Excite, …

29

Classement des moteurs de recherches, Étude menée par la DSI

Service de recherche documentairehttp://www.dsi-info.ca

30

Classement des moteurs de recherches

� Critères de classement :� Les formulaires : voir www.dsi-info.ca� Les requêtes

� 1. Personnage publique� 2. Informatique / télécommunication (logiciel, matériel, jeux...) � 3. Information médicale� 4. Education� 5. Affaires� 6. Science� 7. Information politique et gouvernementale� 8. Passe-temps� 9. Images� 10. Divertissement� 11. Voyage� 12. Arts et humanités

31

00-1 point par dysfonction

Dysfonction d'un champ de recherche ou de fonctions

Dysfonction

00-1 point par doublonDes pages ont des doublons

00-1 pointDes pages ont des codes d'erreurs

Mise à jour / erreur

00-1 point par référenceLa référence n'est pas dans le champ sémantique de la question

Bruit

001 point par référenceLa réponse est àmoins de 19 clics

001 point par référenceLes réponses sont dans le champ sémantique de la question

005 pointsLa réponse est entre la 16e et la 20e références

0010 pointsLa réponse est entre la 11e et la 15e références

0015 pointsLa réponse est entre la 6e et la 10e références

0020 pointsLa réponse est dans les 5 premières références

Pertinence des réponses

Q.BQ.APointageDescriptionCritères

Grille d'évaluation des résultats de recherche

32

Pointage total

251411AltaVista Canada19

281513Excite France18

281612Northern Light17

291217Altavista USA16

301614Lycos France15

301416AltaVista Belgique14

311714Excite Canada13

311417AltaVista France12

321913Lycos Canada11

331716Excite10

342212Lycos USA9

371423Voila8

392019AllTheWeb7

401129HotBot France6

412417Google français5

442420MSN USA4

452421MSN Canada3

452421MSN France2

511734HotBot USA1

TotalRequêtesFormulaireAutomatesRang

Classement des automates de recherche

33

Conclusion

Futur des moteurs de recherche :

� Accès au Web profond� Moteurs de recherche sensible à la sémantique

� Création de moteurs de recherche thématiques

34

Références� [1] Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks.

Science, 286(5439):509-512, October 1999. � [2] Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan,

Raymie Stata, Andrew Tomkins, and Janet Wiener. Graph structure in the web: experiments and models. In Proceedings of the Ninth International World-Wide Web Conference, 2000.

� [3] Reka Albert, Albert-Laszlo Barabasi, and Hawoong Jeong. Diameter of the World Wide Web. Nature, 401(6749), September 1999.

� [4] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In Proceedings of 7th World Wide Web Conference, 1998.

� [5] S. Chakrabarti and S. Muthukrishnan. Resource scheduling for parallel database and scientific applications. In 8th ACM Symposium on Parallel Algorithms and Architectures, pages 329{335, June 1996.

� [6] Junghoo Cho and Hector Garcia-Molina. Estimating frequency of change. In Submitted for publication, 2000.

� [7] Junghoo Cho and Hector Garcia-Molina. Synchronizing a database to improve freshness. In Proceedings of the International Conference on Management of Data, 2000. Available at http://wwwdiglib.stanford.edu/cgi-bin/get/SIDL-WP-1999-0116. 39

� [8] Fred Douglis, Anja Feldmann, and Balachander Krishnamurthy. Rate of change and other metrics: a live study of the world wide web. In USENIX Symposium on Internetworking Technologies and Systems, 1999.

� [9] Bernardo A. Huberman and Lada A. Adamic. Growth dynamics of the World-Wide Web. Nature, 401(6749), September 1999.

� [10] Jon Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5):604{ 632, November 1999.

35

Références (suite)� [11] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Computer Science Department, Stanford University, 1998.� [12] James Pitkow and Peter Pirolli. Life, death, and lawfulness on the electronic frontier. In Proceedings of the Conference on Human Factors in Computing Systems CHI'97, 1997. � [13] Gerard Salton. Automatic Text Processing. Addison-Wesley, Reading, Mass., 1989.� [14] Craig E. Wills and Mikhail Mikhailov. Towards a better understanding of web resources and server responses for improved caching. In Proceedings of the Eighth International World-Wide-Web Conference, 1999.� [15] Ian H. Witten. Managing gigabytes : compressing and indexing documents and images. Van Nostrand Reinhold, New York, 1994. 42 � [16] Arasu, Arvind; Cho, Junghoo; Garcia-Molina, Hector; Paepcke, Andreas; Raghavan, Sriram. Searching the Web, 2000, Stanford University.� [17] Junghoo Cho and Hector Garcia-Molina. Synchronizing a database to improve freshness. In Proceedings of the International Conference on Management of Data, 2000. Available at http://www.diglib.stanford.edu/cgi-bin/get/SIDL-WP-1999-0116.