Chapitre 2 — Chalutiers et tailles du Web

Le monde est de taille moyenne.

La taille ne fait pas tout. La baleine est en voie d’extinction alors que la fourmi se porte bien.

Il faut cacher la profondeur. Où ça ? À la surface.

Maintenant que nous avons défini un cadre sur lequel travailler (le Web accessible), la question de savoir quels objets nous allons étudier se pose. D’un point vue mathématique, le Web accessible peut être infini dénombrable — selon la RFC 2616 [Fie+99] — ou fini — car il n’existe qu’un nombre fini de serveurs et que chacun possède une taille limite d’URL. Il répond en tout cas à une certaine définition physicienne de l’infini, qui est celle que nous utiliserons ici : grand devant le nombre d’atomes de l’univers. Le Web accessible contient en effet beaucoup de nids de pages quasi-infinis. La page qui pointe vers toutes les pages, bien sûr, mais aussi des serveurs mal configurés, ou même des sites commerciaux qui essaient, en créant une infinité de pages, d’augmenter leur PageRank (voir Partie II, Section 7.5). Pour donner une exemple concret, lors de la présentation de leur article Extrapolation methods for accelerating PageRank computations [Kam+03a], les auteurs ont raconté comment une de leur expérience a été perturbée par un site allemand qui occupait 90 % des pages qu’ils avaient indexées. Vérification faite, le site en question était un site pornographique qui espérait grâce à une infinité de pages étroitement reliées entre elles avoir un bon classement dans les moteurs de recherche (principe des Free For All, aussi appelés farm links ou pouponnières).

En conclusion, il est impossible d’indexer tout le Web accessible, de même que parler de sa taille n’a plus de sens¹. En l’absence d’accès physique aux serveurs, les seules données tangibles que nous ayons à notre disposition sont donc les crawls, c’est-à-dire les zones du Web effectivement découvertes, et éventuellement indexées, par des entreprises commerciales (moteurs de recherche) ou des institutions publiques. L’objet de ce chapitre sera de définir précisément les crawls, de donner des ordres de grandeurs, et de voir dans quelle mesure il est possible de comparer des crawls ou de mesurer une certaine qualité.

2.1 Les chalutiers du Web

Les crawleurs, ou spiders, ou agents, sont les chalutiers qui parcourent le Web afin de générer ces morceaux de Web appelés crawls. Il y a deux principaux types de crawleurs : les crawleurs statiques et les crawleurs dynamiques. Le principe de tous les crawleurs statiques est le même : à partir d’un ensemble de pages initial, ils analysent les hyperliens contenus dans ces pages, essaient de récupérer les pages pointées par ces hyperliens, et ainsi de suite, pour récupérer ainsi une partie sans cesse croissante des pages du Web accessible. Chaque page n’est a priori récupérée qu’une seule fois, et on arrête le procédé quand on estime le moment voulu (suffisamment de pages récupérées, croissance devenue négligeable…). Le crawl statique que l’on obtient alors est constitué de :

• un ensemble de pages connues, qui est la réunion de l’ensemble initial et de l’ensemble des pages découvertes ;
• un ensemble de pages indexées, sous-ensemble de celui des pages connues constitué des pages effectivement parcourues par le crawl ;
• un ensemble d’hyperliens issus des pages indexées et pointant vers les pages connues.

Un crawleur dynamique, lui, n’est pas prévu pour s’arrêter, mais pour parcourir perpétuellement le Web et revisiter périodiquement les pages qu’il a parcouru [APC03].

Ce que nous appelons crawleur est en fait l’ensemble des moyens logiciels et matériels permettant de réaliser un crawl. Qu’est-ce qui va faire qu’un crawleur va produire un certain crawl et pas un autre ?

• La date à laquelle le crawl démarre.
• L’ensemble des pages de départ.
• La stratégie d’exploration des nouvelles pages (dans quel ordre récupérer quelles pages ?).
• Les limitations techniques : bande passante, capacité de stockage et de traitement, temps disponible…

Ceci est valable pour tous les types de crawleurs, même si asymptotiquement, seules les stratégies d’exploration et les limitations techniques jouent un rôle important pour les crawleurs dynamiques.

2.1.1 Création de l’ensemble des pages initial

Il va de soi que le choix d’un bon ensemble de départ est fondamental pour l’efficacité d’un crawleur. Pour des raisons commerciales, il est difficile d’obtenir les ensembles de départ des grands moteurs de recherche. Beaucoup de gens s’accordent cependant pour estimer que les grands moteurs de recherche utilisent :

• un sous-ensemble bien choisi de l’ensemble des pages obtenues par les crawls précédents [CGP98]. Les pages d’accueil des annuaires, en particulier, semblent être des candidats de choix pour faire partie de l’ensemble initiale [Cra04] ;
• des nouvelles pages soumises par l’un des nombreux procédés de référencement existants (parfois payants) ;
• il est possible que soient également utilisées quelques techniques plus ou moins rusées pour découvrir des nouvelles pages, comme analyser les logs des serveurs Web, ou essayer de remonter l’arbre des URLs des pages « isolées » (rumeurs lues sur différentes pages du site http://www.webrankinfo.com).

Pour conclure avec le choix de l’ensemble initial, signalons que c’est cet ensemble qui détermine en grande partie la structure de nœud papillon d’un graphe du Web (voir Section 3.2).

2.1.2 Stratégies d’exploration

Un crawleur idéal qui pourrait récupérer et traiter une infinité de pages par unité de temps n’aurait pas de souci pour obtenir tout le Web théoriquement atteignable par hyperliens à partie de l’ensemble initial. Toutes les méthodes de parcours exhaustif (en largeur ou en profondeur par exemple) aboutiraient à un même résultat optimal. Mais les crawlers réels sont limités par leur bande passante, leur capacité de traitement ainsi que le nombre de requêtes par serveur et par minute, qui doit tenir compte autant des règles de politesse que du risque d’être banni.

Toutes ces contraintes font que, à un instant donné, on peut considérer qu’il existe une limite finie au nombre de pages qu’un moteur de recherche précis peut indexer, et il semble que ce nombre ait toujours été, quelque soit le moteur de recherche considéré, assez inférieur aux estimations finies du Web Indexable [Ber00, BB98, Hen+99, LG98, LG99].

Chaque moteur possède donc une barrière physique au nombre de pages qu’il peut indexer. Par exemple, pour et d’après Google, cette barrière est d’environ 4 milliards de documents. La stratégie d’exploration (couplée avec le choix de l’ensemble initial) va décider quels seront ces 4 milliards de pages, et donc dans une large mesure quelle sera la qualité² d’un crawl. Un moteur de recherche dont les agents se perdraient dans les pouponnières et autres pages qui pointent vers toutes les pages aurait sûrement peu de succès. C’est pourquoi certains moteurs, comme AltaVista et Teoma, évitent la pratique du Deep Crawl³, alors que d’autres, comme Google, répertorient les pouponnières dans une liste noire.

La stratégie peut aussi modifier négativement la barrière d’un moteur de recherche, si elle ne cherche pas à optimiser les ressources disponibles. Par exemple, à cause de la limite du nombre de requêtes par site, la bande passante prise par l’exploration d’un serveur est souvent minime devant la bande passante disponible, d’où la quasi-nécessité d’explorer plusieurs serveurs en parallèle. Pour les mêmes raisons, il vaut mieux toujours avoir un serveur rapide parmi les serveurs que l’on est en train de questionner.

Toutes ces contraintes « physiques » prises en compte, on distingue principalement deux philosophies dans les stratégies d’exploration connues.

• Traditionnellement, les moteurs de recherche employaient semble-t-il une exploration de type parcours en largueur, les pages découvertes en premier étant explorées prioritairement (sous réserve des contraintes décrites ci-dessus) [Bro+00].
• Des méthodes d’exploration inspirées des marches aléatoires se développent également (voir [Hen+99] et, dans une certaine mesure, la stratégie greedy de [APC03]). Ces méthodes présentent l’avantage de récupérer plus facilement les pages importantes au sens du PageRank [Hen+99], voire d’estimer le PageRank de manière dynamique [APC03]. Les liens entre PageRank et marche aléatoire seront développés lors de la Partie II.

2.2 Tailles et évolutions des crawls

Maintenant que le concept de crawl a été grossièrement expliqué, nous allons donner quelques statistiques sur les ordres de grandeur considérés lorsque l’on parle de crawl pour les principaux moteurs de recherches.

2.2.1 Selon les organisateurs

Ces données ont pour la plupart été obtenues sur le site http://searchenginewatch.com/.

La Figure 2.1 présente les tailles revendiquées des cinq moteurs de recherche milliardaires à la date du 2 septembre 2003. Si on étudie l’évolution respective des différents moteurs de recherche, on peut distinguer plusieurs grandes périodes de bouleversement, qui correspondent à des périodes de compétition intense entre les moteurs. Ces guerres du Crawl sont représentées en détail Figure 2.2. Chacune de ces guerres s’est soldée pour le ou les vainqueurs par le franchissement d’une barre psychologique.

Entre décembre 1997 et juin 1999 a lieu la première guerre du Crawl, à l’issue de laquelle AltaVista dépasse la barre des 150 millions, talonné de près par NorthernLight (Figure 2.2b).

La deuxième guerre du crawl (septembre 1999 – juin 2000) est marquée par un match serré entre Altavista et AllTheWeb, qui se conclut par la victoire écrasante de… Google, qui va se développer jusqu’à dépasser le milliard et demi de pages revendiquées, ce qui impose un nouveau standard (Figure 2.2c).

La troisième guerre (juin 2002 – décembre 2002) débute par un court passage d’AllTheWeb en tête de course. Google et Inktomi ripostent presque aussitôt, et en l’espace de six mois franchissent le cap des 3 milliards de pages web. Quelques mois plus tard, AllTheWeb se remet au diapason (Figure 2.2d).

Actuellement (été 2004), Google affirme indexer plus de 4 milliards de pages, mais le champ de bataille s’est déplacé. La bataille entre Google et Yahoo (qui sous-traitait avec Google jusqu’en février 2004, et qui depuis utilise la base de donnée d’Inktomi) essaie de se faire plus subtile, le but étant d’avoir les résultats « les plus compréhensibles et les plus pertinents ». Yahoo préparerait d’ailleurs sa propre version du PageRank de Google, le WebRank.

2.2.2 Selon la police

Tous les chiffres que nous venons de voir sont ceux annoncés par les moteurs de recherche eux-mêmes. Comme nous sommes dans un contexte de concurrence commerciale, il est légitime de s’interroger sur la fiabilité de ces chiffres, avec le problème de définir une méthodologie adéquate.

Le site SearchEngineShowdown [Sea], administré par Greg Notess, propose une méthode d’estimation grossière de la taille effective des moteurs de recherche. Le principe est d’effectuer plusieurs requêtes parallèlement sur les différents moteurs de recherche que l’on veut comparer, et de postuler que le nombre de réponses renvoyées par chaque moteur est en première approximation proportionnel au nombres d’URLs connues par le moteur de recherche. Si l’on connaît la taille réelle d’un des moteurs, on peut alors par une simple règle de trois estimer la taille réelle des autres moteurs. Or, en décembre 2002, il était possible de connaître la taille exacte du moteur AllTheWeb simplement en soumettant la requête url.all:http⁴.

La Figure 2.3 compare les tailles revendiquées et estimées par la méthode de Greg Notess de plusieurs moteurs de recherche. On peut facilement distinguer trois catégories de moteur de recherche, qui montrent autant les éventuelles exagérations des moteurs que le biais introduit par les requêtes :

Les réalistes

Google, AllTheWeb et WiseNut ont des valeurs estimées et revendiquées extrêmement proches, et tendent à prouver que la méthode d’estimation présente une certaine fiabilité.

Les sites qui voulaient trois milliards

Les estimations des taille de HotBot et MSN Search sont en nette contradiction avec les valeurs revendiquées. Il s’agit de moteurs basés sur la technologie Inktomi. Selon Inktomi, tous les ordinateurs formant leur base de données ne sont pas accessibles en même temps, et donc on ne peut jamais accéder à la totalité de la base. De plus, il est possible que les partenaires d’Inktomi (HotBot et MSN Search dans le cas présent) n’utilisent qu’une partie de la base de données, pour des raisons pratiques ou commerciales. Pour Greg Notess, ces estimations reflètent donc la portion de la base de données réellement disponibles au moment où les requêtes ont été faites. Il est évident que le biais de la méthode de Notess nous empêche de faire des affirmations catégoriques, mais l’on ne peut s’empêcher de soupçonner le chiffre de trois milliards d’être une réponse publicitaire aux trois milliards de Google (rappel : nous sommes à la fin de la troisième guerre du Crawl).

Les modestes

AltaVista, Teoma, NLResearch et Gigablast semblent revendiquer beaucoup moins que leur taille réelle, ce qui ne semble guère logique. D’après Greg Notess, l’explication de ce paradoxe vient de la façon de comptabiliser les pages connues, mais non-indexées. En effet, les sites que nous avons appelés réalistes semblent revendiquer leurs URLs connues, indexées ou non, alors que les modestes se restreignent aux pages effectivement indexées. Quand on sait que les pages non-indexées représentent au moins 25 % des pages connues, mais moins de 1 % des réponses aux requêtes⁵ (sources : SearchEngineShowdown), on a un début d’explication du phénomène.

2.2.3 Remarques personnelles

Avant de continuer plus loin, je voudrais mettre en avant un constat personnel de l’extrême volatilité des chiffres avancés par les moteurs de recherche. Par exemple, alors que le nombre d’URLs revendiquées par Google est de quatre milliards, la requête « the »⁶ promet pages. D’un autre côté, il est en théorie possible de connaître le nombre de pages connues pour un domaine précis (par exemple .fr) en employant une requête du type site:tld. En faisant cette opération sur l’ensemble des TLDs, on devrait logiquement tomber sur près de six milliards de pages, voire plus. Cependant, l’expérience ne nous en donne que (à 0,26% près, Google ne donnant que 3 chiffres significatifs). Il faut conclure de ces deux tests soit qu’au moment des expériences, Google indexait au moins pages et au plus , soit que plus de 5 milliards de pages indéxées n’appartiennent pas à des TLDs existant, soit que les chiffres annoncés par Google doivent être pris avec un minimum de réserve.

Le nouveau moteur de recherche de Yahoo donne lui aussi des résultats parfois étranges. Ainsi, j’ai pu constater que le nombre de résultats pouvait dépendre du rang à partir duquel on désirait voir les résultats. Ainsi, alors que la requête "pâte à crêpes" donne réponses si on affiche les premières pages, ce nombre tombe à si on demande les pages à , avec une décroissance régulière. Expérimentalement, la différence peut atteindre 5% du chiffre annoncé.

Il faut enfin ne pas oublier de parler du problème des doublons. En effet, la plupart des grands moteurs considèrent pour leurs index et algorithmes que www.domain.com/, domain.com/, et www.domain.com/index.html sont des pages différentes. Le regroupement est fait a posteriori, en utilisant des méthodes de hashage pour identifier les pages identiques (que Google appelle pudiquement pages à contenu similaire). En résumé, les doublons sont comptés dans le nombres de pages trouvées, mais ne sont pas renvoyés dans les réponses (sauf demande explicite de l’utilisateur). Pour fixer les idées, le Tableau 2.1 présente les résultats de quelques requêtes pour lesquelles il est possible de connaître le nombre de pages hors doublons⁷. Par convention, nous avons choisi de définir le nombre de pages revendiquées par Yahoo comme celui revendiqué lorsque l’on demande les dernières pages.

2.3 Mesures sur des crawls

L’étude et la comparaison des différents crawls est un sujet délicat à traiter. D’un côté, il y a les crawls commerciaux issus de moteurs de recherche, qui ne peuvent guère être accessibles qu’au travers de requêtes publiques faites sur les moteurs eux-mêmes, lesquelles requêtes sont très souvent bridées. De l’autre, les laboratoires de recherche offrent souvent des tailles plus réduites et des méthodes de crawl extrêmement variées. À cause de ces disparités, il peut être difficile de comparer différents résultats, voire de savoir s’ils sont comparables. L’objet de cette section est de répertorier différentes méthodes d’évaluation des crawls, dans le cas de données privées et celui de données publiques.

La méthode d’estimation des tailles réelles proposée par Greg Notess (cf Section 2.2.2) peut également servir de mesure de qualité de crawl. En dénombrant les réponses faites à 25 requêtes représentatives, on mesure en effet en quelque sorte la capacité d’un moteur à répondre à ces requêtes, transformant en quelque sorte le biais des requêtes en mesure de qualité.

2.3.1 Techniques de chevauchement (overlap)

Ce système de comparaison par requêtes est utilisé de manière plus poussé dans la méthode de comparaison par chevauchement, introduite par Bharat et Broder en 1998 [BB98] et reprise par Lawrence et Giles [LG98, LG99].

Le principe du chevauchement est le suivant : arriver à mesurer entre deux moteurs le chevauchement de leurs index respectifs. Par exemple, si on peut déterminer qu’une fraction d’un index est dans , et si une fraction de est dans , alors on peut en déduire que , et ainsi avoir le rapport de taille entre les index :

Tout le problème est d’estimer et en l’absence d’index librement accessible au public. C’est là qu’intervient l’échantillonnage par requête : des requêtes créées par un générateur aléatoire le plus uniforme possible, sont soumises à un moteur. À chaque fois, un des réponses parmi les 100 premières est choisie au hasard, et on vérifie, par des méthodes plus ou moins strictes, si cette réponse est dans l’index de l’autre moteur.

Par rapport à la méthode de Notess, deux autres sources de biais (en plus du biais dû au choix des requêtes et des biais standards d’échantillonnage) sont introduites :

Le biais de classement

En choississant uniquement les échantillons parmi les 100 premières réponses (contrainte imposée par les moteurs de recherche eux-même), les classements (les importances) des pages considérées sont statistiquement plus élevés que la moyenne.

Le biais de vérification

Il n’y a pas de méthode parfaite pour contrôler l’appartenance d’une page donnée à un index. Les différentes méthodes proposées par Bharat et Broder sont basées sur l’analyse d’une requête censée définir la page et les critères de validation vont de le moteur renvoie la bonne page à le moteur revoie un résultat non vide.

Les mesures par chevauchement ont eu leur heure de gloire au cours des guerres du Crawl⁸ (voir Section 2.2), mais si elles ont l’avantage d’introduire un formalisme rigoureux, le coût en biais et la relative complexité de la méthode font que la méthode de Notess reste très compétitive.

2.3.2 Échantillonnage par marche aléatoire

Une variante intéressante de la méthode d’échantillonnage de Bharat et Broder a été proposée par Henzinger et al. [Hen+99] : plutôt que de mesurer un moteur à l’aide d’un autre, le principe est d’utiliser comme mètre-étalon un crawl personnel issu d’une marche aléatoire. Cette marche aléatoire ne fournit pas un échantillonnage uniforme des pages Web⁹, mais un échantillonnage qui, aux biais statistiques près, obéit à la distribution de probabilité associée à la marche aléatoire. Cette distribution sur les pages Web, plus connue sous le nom de PageRank (Voir la Partie II), va permettre, en mesurant à l’aide des techniques de chevauchement la fraction des échantillons connus du moteur, d’estimer la quantité de PageRank contenue dans les pages connues du moteur.

Le biais spécifique de cette méthode est que derrière l’échantillonnage par marche aléatoire se cache un crawl implicite, le crawl que l’on obtiendrait en laissant tourner la marche aléatoire suffisamment longtemps. On mesure donc le PageRank du moteur que l’on veut tester par rapport au PageRank sur ce crawl virtuel. En particulier, toute divergence entre les stratégies de crawl de la marche aléatoire et du moteur sont néfastes pour l’évaluation de ce dernier : si le moteur a indexé des parties du Web que la marche aléatoire, pour diverses raisons techniques, n’a jamais effleurées, ces parties ne compteront pas dans l’évaluation. À l’inverse, si certains sites sont volontairement évités par les moteurs (des pouponnières par exemple, voir Section 2.1.2), cette omission sera sanctionnée dans l’évaluation.