FLASH INFORMATIQUE FI



Indexation du domaine epfl.ch - Google vs. Inktomi




Francis LAPIQUE


Introduction

Il ne s’agit pas d’un combat singulier, mais d’expliquer dans un premier temps comment l’approche de ces deux moteurs de recherche peut être complémentaire ou du moins de comprendre pourquoi la même requête peut donner des résultats très différents. Les deux moteurs (Google et Inktomi) sont accessibles depuis les boîtes outils de rechercheprésentes dans les pages Web de l’EPFL. Pour mémoire, rappelons que la recherche Google est dans ce cadre, limitée aux serveurs du domaine epfl.ch, il ne s’agit donc pas d’une recherche telle que celle exécutée via les sites www.google.ch ou www.google.com.

A titre d’exemple voici les résultats obtenus le 10 février (à une autre date ils peuvent être sensiblement différents) en cherchant la chaîne EPFL avec les deux moteurs. Un résultat est-il plus juste ou plus pertinent qu’un autre ?

Résultats avec Google

EPFL Main entrance
The EPFL offers 13 complete study courses in Engineering, Basic Sciences and Architecture. ... a person. a place. epfl.ch with Google. epfl.ch with Inktomi. ...
www.epfl.ch/Eindex.html - 14k - 8 Feb 2004 - Cached - Similar pages

EPFL Entree principale
Depuis 2002, la totalité de l’EPFL est réunie sur un seul site, dans une nouvelle organisation. Etudiants, chercheurs, architectes ...
www.epfl.ch/ - 14k - 8 Feb 2004 - Cached - Similar pages

I&C
Homepage of the School of Computer and Communication Sciences at EPFL - Swiss Federal Institute of Technology Lausanne. ... a person. a place. epfl.ch with Google. ...
ic.epfl.ch/ - 38k - 8 Feb 2004 - Cached - Similar pages

Visible Human Server
EPFL Visible Human Server - Provides applications to extract slices, surfaces, animations, 3D scenes extracted from the Visible Human Datasets. ...
visiblehuman.epfl.ch/ - 15k - Cached - Similar pages

GNUWin II : Open your Windows
... As most of us are Linux users it is difficult for us to test new applications. Any help would be appreciated. Please contact gnuwin@epfl.ch ...
gnuwin.epfl.ch/ - 3k - Cached - Similar pages

Résultats avec Inktomi

EPFL Entree principale
Depuis 2002, la totalité de l’EPFL est réunie sur un seul site, dans une nouvelle organisation. Etudiants, chercheurs, architectes, entrepreneurs, collaborateurs techniques et administratifs, soit ...
http://www.epfl.ch/
14KB, 02/02/04, Pages similaires

ENAC Accueil
Home page de la faculté ENAC, EPFL
http://enac.epfl.ch/
54KB, 08/02/04, Pages similaires

Bienvenue à la FSB
Notre faculté assure l’enseignement de la chimie, des mathématiques et de la physique, ainsi que d’autres domaines des sciences de base pour toutes les sections de l’EPFL.
http://sb.epfl.ch/
45KB, 07/02/04, Pages similaires

EPFL Place centrale
Depuis 2002, la totalité de l’EPFL est réunie sur un seul site, dans une nouvelle organisation. Etudiants, chercheurs, architectes, entrepreneurs, collaborateurs techniques et administratifs, soit ...
http://www.epfl.ch/place.html
25KB, 04/02/04, Pages similaires

Faculte STI Sciences et Techniques de l’Ingenieur
Ecole Polytechnique Federale de Lausanne - Swiss Federal Intitute of Technology in Lausanne - Faculte STI Sciences et Techniques de l’Ingenieur - School of Engineering Sciences
http://sti.epfl.ch/
23KB, 02/02/04, Pages similaires

Pourquoi ces différences et comment travaillent ces moteurs ?

Avec Google, nous interrogeons les 303’000 pages du domaine epfl.ch indexées par la machinerie Google dans le cadre de leur programme : University Search Customizable Google Free (vous pourriez obtenir un résultat identique via www.google.com en ajoutant la directive site : .epfl.ch à votre requête).
Avec Inktomi, nous interrogeons les 375’000 pages que nous avons indexées localement et qui se trouvent sur la machine mysearch.epfl.ch.
Les deux moteurs s’accordent sur la première page trouvée, à la langue près : la home page de l’EPFL, dans sa version anglaise pour Google, dans sa version française pour Inktomi. La suite est plus déroutante : le site Visible Human Server, bien placé par Google, les facultés ENAC, SB et STI bien placées par Inktomi. On peut n’être satisfait ni par l’un, ni par l’autre. L’absence de marqueurs sémantiques décrivant les contenus et les fonctionnalités de nos ressources Web, fait que ces deux moteurs nous imposent chacun leur point de vue.

En attendant un accès plus intelligent à nos ressources Web, un peu d’histoire :
Inktomi, fondée en 1995 fait partie des pionniers. A la base des moteurs tels que HotBot, MSN et Yahoo ! , il occupe la première place jusqu’en juin 2000 quand Google le remplace ; il la retrouvera en 2003 par son rachat par Yahoo ! qui acquiert dans la foulée Ouverture.
Inktomi s’appuie sur des méthodes statistiques. Documents et requêtes sont exprimés comme des vecteurs (de termes). Ils sont classés en fonction de leur proximité avec la requête. Inktomi exploite les fameuses balises title et meta qui permettent au référenceur d’indiquer une liste de mots-clés et une description sensée correspondre au contenu du site. Malheureusement, cette dernière balise fût bien vite détournée de son usage. Inktomi compte une extension probalistique en proposant un moteur bayésien. Ces méthodes bayésiennes sont de plus en plus populaires car elles sont à la base de nombreux filtres anti-spam. Nous reviendrons dans un prochain article sur ces méthodes bayésiennes et le rôle qu’elles peuvent jouer dans le vaste sujet du Web sémantique.
Côté Google, tout le monde connait l’extraordinaire aventure de Larry Page et Sergey Brin, deux étudiants provenant respectivement des facultés de Mathématique et d’Informatique de l’Université de Stanford. Ils conçoivent et gèrent un projet de recherche qui mène à la création de Google. Les années 1999-2000 marquent les premiers succès. America On Line, avec 34 millions de clients et 10 millions de visiteurs par jour, signe un accord qui le lie à la technologie Google. Aujourd’hui, Google est synonyme de la recherche sur Internet, avec un index de plus de 3 milliards de pages. A titre d’information, Google vient d’ouvrir un centre R&D à Zurich (voir www.google.ch/jobs/).
Au lieu de considérer le Web comme un ensemble de documents atomiques et indépendants, L. Page et S. Brin vont l’exploiter comme un immense graphe. Première idée. Deuxième idée, à l’image de ce qu’ils vivent dans le monde académique où poids d’un article et fréquence de citations vont de pair, ils introduisent le concept de PageRank (PR) : tout lien pointant de la page A à la page B est considéré comme un vote de la page A en faveur de la page B. [...] Google ne limite pas son évaluation au nombre de votes (liens) reçus par la page, il procède également à une analyse de la page qui contient le lien. Les liens présents dans des pages jugées importantes par Google auront plus de poids, et contribueront ainsi à élire d’autres pages.
Ces idées vont bouleverser le paysage des moteurs de recherche et en filigrane l’histoire d’Internet. Le célèbre article de Brin et Page en 1998, The Anatomy of a Large-Scale Hypertextual Web Search Engine, et le non moins célèbre article de Jon M. Kleinberg, Authoritative Sources in a Hyperlinked Environment, marquent bien les préocupations de ces chercheurs pour l’étude des graphes réels.
L’approche de Kleinberg (reprise dans le projet CLEVER) consiste à calculer la popularité (=Hub) et l’autorité (=Authority) d’un document. L’hypothèse : un document qui pointe vers beaucoup de bonnes Authorities est un bon Hub, et un document pointé par beaucoup de bons Hubs est une bonne Authority . Les Hubs et les Authorities sont calculés dans un processus itératif de la façon suivante :

        AuthorityScore (p) = somme ( HubScore(q) )
                all q linking to p
        HubScore (p) = somme ( AuthorityScore(r) )
                all r linking from p

Les Hubs et les Authorities sont initialisés à 1. Ces sommes convergent assez rapidement.
L’algorithme du PageRank fait l’objet de nombreux articles. J’en cite trois dont je me suis largement inspiré : l’Algorithme du PageRank expliqué, inspiré du non moins excellent article de Ian Rogers, The Google Pagerank Algorithm and How It works, et Utiliser les liens pour adapter les moteurs de recherche aux spécificités du Web, S. Radhouani, J.-P. Chevallet.

Comme il a été mentionné plus haut, l’approche de Brin et Page est basée sur la notion de propagation de popularité. Citons Radhouani et Chevallet : Le principe est d’évaluer l’importance d’une page en fonction de chaque page pointant vers elle. La propagation met en avant les pages qui jouent un rôle particulier dans le réseau des liens, avec l’hypothèse : une page référencée par un grand nombre de pages est une bonne page. Cette mesure est une distribution de probabilité sur les pages. Elle mesure en fait la probabilité PR pour un internaute naviguant au hasard, d’atteindre une page donnée P. Cette probabilité est d’autant plus forte que le nombre de pages qui réfèrent P est important. PR est donc fonction de la somme des probabilités des pages qui référencent P. Il faut aussi tenir compte du fait que les pages qui référencent P ont d’autres liens sortant vers d’autres pages que P. Il faut alors diviser cette probabilité par le nombre C de liens sortant des pages qui référencent P. Finalement, il faut tenir compte du fait qu’un internaute peut arriver sur une page quelconque sans suivre de liens (à partir de ses signets par exemple). La formule proposée [Brin, 1998] tient ainsi compte de la probabilité de suivre effectivement les liens. La probabilité d’arriver à la page P sans suivre de lien est donc de (1-d). La formule de calcul du PageRank est alors la suivante :
PR(P) = (1-d) + d[(PR(P1)/C(P1) + ... + (PR(Pm)/C(Pm))]
Avec d, facteur d’amortissement 0 C(Pj) = nombre de liens sortant de la page P
PR(P) : PageRank de la page P

Dans la pratique, comment ça marche ?

Reprenons un exemple de l’article L’algorithme du PageRank expliqué avec quatre pages liées et un facteur d’amortissement de 0.85 :

JPEG - 8.1 ko
Figure 1

Dans cet exemple, nous avons un site comprenant quatre pages, dont une ne recevant aucun lien (la page D).
Le PR de la page D sera donc de 0.15, grâce au premier terme de la formule du PageRank (1 - d). Bien qu’ayant un PR calculé, il est vraisemblable que cette page disparaîtra de l’index Google très vite, n’ayant aucun lien entrant.

Au bout d’une vingtaine d’itérations, les valeurs de PR pour nos pages convergent vers les valeurs suivantes :

Page A 1.49
Page B 0.78
Page C 1.58
Page D 0.15
Somme des PageRank 4.0
Moyenne 1.0

Nous voyons que dans notre exemple, la page C a le PR le plus élevé. C’était prévisible dès l’examen du graphique, elle reçoit un lien entrant des pages A, B et D, et n’en émet qu’un seul vers la page A.
Google est très discret sur le temps et les algorithmes de calcul du PageRank car le graphe réel possède plusieurs milliards de noeuds. La figure suivante montre un diagramme simplifié de l’architecture du moteur. Elle comprend une partie classique d’indexation des pages et son extension PageRank. Le résultat final est une combinaison savante entre la proximité de la requête, le contenu des pages indexées et le PageRank.

JPEG - 10.6 ko
Figure 2

Des développements sont en cours pour donner plus d’importance aux pages bénéficiant de liens en provenance de sites dont on connait la thématique de départ.
En revenant à notre exemple du début, notre recherche EPFL, Google et Inktomi donnent pratiquement la même page car le classement proposé par le moteur d’indexation n’a pas drastiquement été remis en cause par le PageRank.

Statistiques vs popularité ?

En fait en exploitant ces deux moteurs sur le domaine epfl.ch, nous projetons l’ensemble de nos informations sur deux axes : un axe sensible à la statistique (présence, poids des mots, ...), un autre sensible bien évidemment à cet aspect, mais pondéré par la popularité de l’information. Cette décantation de l’information est très intéressante comme peut le montrer l’exemple d’une requête plus technique comme bose condensation :

Avec Google

Bose-Einstein Condensation with Attractive Interactions
[E12.03] Bose-Einstein Condensation with Attractive Interactions. Peter Higley, DJ Thouless (University of Washington). Most of the ...
epswww.epfl.ch/aps/BAPSMAR98/ab... - 3k - Cached - Similar pages

Bose-Einstein Condensation of Excitons in Quantum Well with Donor ...
... Los Angeles Convention Center. [K32.06] Bose-Einstein Condensation of Excitons in Quantum Well with Donor Impurities. JF Jan, YC Lee ...
epswww.epfl.ch/aps/BAPSMAR98/ab... - 3k - Cached - Similar pages

Seminars at IPMC
... finite magnetization. Antiferromagnetic ordering may occur due to Bose condensation of magnetic excitations. Some materials exhibit ... ipmc.epfl.ch/Jahia/site/ipmc/cache/offonce/pid/9152 - 75k - Cached - Similar pages

Monday afternoon, 16 March 1998
... and University of Toronto), A. Griffin (University of Toronto) 16:06 E12.09 Bose condensation in trapped hard sphere bosons as a function of density Jonathan L ...
epswww.epfl.ch/aps/BAPSMAR98/to... - 101k - Cached - Similar pages

Lectures.html
... composite bosons from a general perspective and present the quantum kinetic description of condensate formation and the Bogoluibov theory of Bose condensation. ...
dpwww.epfl.ch/conferences/Carg... - 20k - Cached - Similar pages

et avec Inktomi

Seminars at IPMC
english only EPFL < FSB < Bienvenue à l’IPMC < Seminars at IPMC Print | Login 2004 2002 - 2003 Jeudi 18 decembre 2003, 16h15, Salle H33, Bâtiment Physique (EPFL) Prof. Gelsomina di Stasio Department of Physics,...
http://ipmc.epfl.ch/page9152.html
75KB, 08/02/04, Pages similaires

Microsoft Word - 2e Cycle 2002_
EPFL ?SECTION DE PHYSIQUE LIVRET DES COURS 2ème Cycle du 5ème semestre au 8 ème semestre Année académique 2002-20032 EPFL ?SECTION DE PHYSIQUE LISTE DES COURS 5 ème et 6 ...
http://dpwww.epfl.ch/cours/2emeCycl...
409KB, 12/08/02, Pages similaires

http://dpwww.epfl.ch/seminars/next_...
Colloque de Physique AVCP - UNIL - EPFL Lundi, 09 Décembre 2002 Auditoire CE 2, 17:15 « Long-Range Transport of Excitons in Quantum Wells - Bose-Einstein Condensation ? » Prof. David W. ...
http://dpwww.epfl.ch/seminars/next_...
2KB, 09/12/02, Pages similaires

http://dpwww.epfl.ch/seminars/next_...
Séminaire FSB de la Section de Physique Lundi, 12 May 2003 Auditoire CE 2, 17:15 « Bose-Einstein condensation on a microchip : Integrated matter-wave optics » Dr J. Reichel Sektion Physik, MPQ / ...
http://dpwww.epfl.ch/seminars/next_...
2KB, 12/05/03, Pages similaires

Microsoft Word - LC_2003_2004_S
ÉCOLE POLYTECHNIQUE FÉDÉRALE DE LAUSANNE SECTION DE PHYSIQUE LIVRET DES COURS 2003 -20042 EPFL ?SECTION DE PHYSIQUE CONTACTS Pour de plus amples informations vous pouvez ...
http://sb2.epfl.ch/SPH/LC_2003_2004...
580KB, 12/08/03, Pages similaires

Google met en avant un abstract d’une conférence intitulé Bose-Einstein Condensation with Attractive Interactions faisant partie d’un Meeting of The American Physical Society March 16-20, 1998.

Inktomi pour sa part met en avant un séminaire du Mardi 27 mai 2003, 16h15, salle H-33, Bâtiment Physique.
La page dpwww.epfl.ch/cours/2emeCycleP... ignorée par Google compte un signal statistique très fort « ...Bose condensation... Refroidissement d’atomes par laser. Condensation de Bose. Radiation pressure. Atom laser cooling. Bose condensation..... ». C’est un document destiné aux étudiants , comme l’indique la présence du mot cours dans l’url.

Dans l’avenir il nous faudra exploiter ces diversités de point de vue et en imaginer d’autres comme différents axes sémantiques qui nous aideront à fixer, partager et formaliser le sens des documents. Dans un prochain article nous montrerons comment une exploitation plus fine de nos deux moteurs Inktomi et Google peuvent significativement améliorer la qualité des réponses.

Pour conclure et montrer combien nous avons à portée de main une mine d’or d’information, nous avons réalisé l’étude pendant quelques jours du graphe des relations du domaine .epfl.ch avec l’extérieur pour quelques sites en appliquant un calcul de PageRank tenant compte de la thématique de la recherche. C’est une piste que l’on pourrait poursuivre pour l’ensemble de l’EPFL pour donner une cartographie de ranking..



Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.