PDF de programación - Resumen Tema 2: Crawling

Resumen Tema 2: Crawling

José Alberto Benítez Andrades

Diciembre 2010

En este trabajo se resumen las conclusiones obtenidas después de haber realizado la lectura de los
artículos propuestos de Sergy Brin amf Lawrence Page, Junghoo Cho, Héctor García-Molina, además
de los que tratan sobre el rastreador Mercator, escritos por Allan Heydon y Marc Najork.

1.

Introducción : Qué es un crawler.

Un crawler (rastreador) es un programa que recupera páginas web, comunmente usado por los
motores de búsqueda [Pinkerton 1994]. Los rastreadores comienzan por una web inicial, que podemos
llamar P0, recuperan esta página, extraen las URLs que se encuentran en su interior, y agregan estas
URLs a una cola para ser rastreadas. Una vez hecho esto, el rastreador recoge las URLs de la cola en
cualquier orden, y repite el proceso. Cada página que es escaneada es dada a un cliente que guarda
las páginas, crea un índice para las páginas o guarda y analiza los contenidos de las páginas.

Los rastreadores son utilizados especialmente por los motores de búsqueda. A lo largo de estos
años, lo que siempre han intentado e intentan, es proporcionar la información más correcta y adecuada
a la búsqueda que realiza el usuario por un término concreto. Para conseguir esto, cada motor de
búsqueda ha realizado sus propios estudios para la aplicación de diferentes algoritmos de recuperación
de información, de indexación de páginas, de lecturas de contenido, etc.

Debido al gran número de páginas web que hay, y sobre todo, al crecimiento constante diario de
las mismas, los rastreadores intentan que sus rastreos sean cada vez más rapidos, que además, la
información que recojan, sea comprimida lo máximo posible y las estructuras de datos sean elegidas
con buen criterio, para que el espacio sea utilizado de forma correcta y eciente.

En los documentos que se proponen de lectura para poder realizar este resumen, se citan algunos de
los rastreadores más importantes a lo largo de estos años, incluso se presentan diferentes comparativas
de rendimiento, habiendo ejecutado varias pruebas con cada uno de ellos.

Algunos de los rastreadores que se citan son los siguientes:

Matthew Gray's Wanderer: fue el primer rastreador creado en la primavera del 1993, coin-
cidiendo con la primera versión del NCSA Mosaic.1

Google: Se dice de él, que es escalable, que indexa de forma eciente y que posee unas estructuras
de datos optimizadas ( según el artículo The Anatomy of a Large-Scale Hypertextual Web Search
Engine, de Sergey Brin y Lawrence Page ). Este rastreador se compone de un conjunto de
servidores con una función concreta:

1NCSA Mosaic: Fue el segundo navegador gráco disponible para visualizar páginas web y el primer navegador gráco

para Microsoft Windows.

1

• URLServer : envía listas de URLs para ser extraídos por los rastreadores.
• StoreServer : recibe las URLs extraídas, las comprime y las almacena en un repositorio.
• Cada página tiene asociado un ID que se llama docID y que es asignado cada vez que una

nueva URL es analizada.

• La indexación es ejecutada por el indexador y el sorter. Además el indexador ejecuta una
serie de funciones: lee el repositorio, descomprime los documentos y los analiza. Cada docu-
mento es convertido en un conjunto de palabras llamados hits. El indexador distribuye los
hits en un conjunto de barriles creando un forward index parcialmente ordenado. Analiza los
enlaces externos y las palabras de anclaje que hay en cada web, almacenando la información
importante en el chero de anclaje. Este chero contiene información que determina dónde
apunta cada enlace y el texto del enlace.

• URLresolver : lee el chero de anclajes y convierte URLs relativas en absolutas y las intro-
duce en docIDs. Se genera una base de datos con pares de docIDs y estos son usados para
computar el PageRank.

• Sorter : Finalmente se encarga de ordenar los barriles.

The Internet Archive: Es otro rastreador alternativo, que es comparado con el rastreador
Mercator en el texto de Allan Heydon y Marc Najork. Usa múltiples máquinas para rastrear la
web, a cada proceso de rastreo se le asigna hasta 64 sitios para rastrear y ningún sitio se le asigna
a más de un rastreador.

Mercator : Rastreador escalable, extensible y modular, realizado en JAVA2. Realizando una
comparativa con los dos rastreadores anteriores, se demostró que era mucho más eciente, ya
que, consumía menos recursos, logro descargar más páginas por segundo, a mayor velocidad y
con más probabilidad de acierto. Además, la creación de módulos hizo bastante atractiva su
utilización, ya que, sin tener que reprogramar el núcleo del rastreador.

WebFountain (Edwards y otros., 2001) es un rastreador distribuido, modular parecido a Mer-
cator desarrollado en el lenguaje C++. Parte una máquina "controladora que coordina con
una serie de máquinas hormiga. Después de descargar las páginas, se deduce para cada página
una tasa de cambio, también llamada, índice de actualización, y se debe utilizar un método de
programación no lineal para solucionar un sistema de ecuaciones para logar la máxima frescura.

PolyBot [Shkapenyuk y Suel, 2002] es un rastreador distribuido escrito en C++ y en Python,
compuesto por un encargado del crawling, uno o más descargadores y uno o más Encargados
de resolver DNS. Las URLs recogidas se añaden a una cola en disco, y se procesa más adelante
para buscar URLs de forma no continua. Posee una función que determina si un dominio es de
segundo o tercer nivel (Por ejemplo: www.indipro.es y www2.indipro.es.com son terceros dominios
del nivel).

WebRACE (Zeinalipour-Yazti y Dikaiakos, 2002) es un módulo de crawling implementado en
Java, y usado como una parte de un sistema más genérico, eRACE. El sistema recibe peticiones
de los usuarios para descargar páginas web, actuando el rastreador como un servidor inteligente.
El sistema también maneja los pedidos suscripciones a las páginas web que deben ser super-
visados: cuando las páginas cambian, deben ser descargadas por el crawler y el suscritor debe

2Lenguaje de programación orientado a objetos, desarrollado por Sun Microsystems a principios de los años 90.

2

ser informado. La característica más excepcional de WebRACE es que, mientras que la mayo-
ría de los crawlers comienzan con un sistema de la semilla URLs, WebRACE está recibiendo
continuamente URLs nuevos para comenzar.

• Ubicrawler (Boldi y otros., 2004) es un rastreador distribuido escrito en Java, y no tiene
ningún proceso central. Se compone de un número de agentes idénticos; y se calcula la
función de la asignación usando el hashing consistente de los nombres de antrión. Hay
superposición cero, signicando que no se recolecta ninguna página dos veces, a menos que
un agente de arrastre se estrelle (entonces, otro agente debe recolectar las páginas del agente
que falla). El crawler se diseña para alcanzar escalabilidad alto y para ser tolerante a los
fallos.

2. Problemas que intenta resolver un crawler.

El objetivo principal que tienen todos los rastreadores, es el de seleccionar las URLs con la in-
formación más exacta sobre la consulta que realiza el usuario. Pero para conseguir esto, además de
encontrarse con una serie de desafíos técnicos, se encuentra con el problema de seleccionar las páginas
más importantes y ordenarlas en función de la información que contienen.

Los crawlers intentan conseguire que las páginas que tienen una mayor relevancia sean visitadas
con anterioridad de las que teienen poca relevancia. Para ello, debe conocer un valor por el cual sean
las páginas rankeadas y surgieron diferentes tipos de Ranking:

Similitud a la consulta Q : Siendo P una web y Q una consulta, se convierten en vectores y se
comparan su similitud en las palabras que contienen cada una.

Backlink Count : Analizando el número de enlaces que existen a la web P. A mayor número de
enlaces, mejor posición.

PageRank : Algoritmo que calcula el ranking de una web, teniendo en cuenta diferentes paráme-
tros, como por ejemplo, el número de enlaces que hay hacia la web, número de enlaces salientes
que hay y también la información que contiene la web, el contenido, entre otros parámetros.

Forward Link Count : Número de enlaces que emanan de P.

Location Metric : Recalca la importancia de la localización de la web a la hora de realizar un
rastreo. Para alguien que se encuentra en España, le interesarán webs que estén en España, antes
que encontrar webs que sean Rusas, por ejemplo.

Pero además de la importancia de la métrica, para conseguir el objetivo que se marcan los rastreadores,
existen diferentes métodos de rastreo. Ya que, no es posible conocer el valor real de ranking de cada
web, pero sí un valor aproximado, existen 3 modelos de rastreo que intentan lograr rastrear las webs
con más relevancia antes que las que no lo tienen:

Crawl & Stop : Un rastreador C comienza en una página P0 y para después de visitar K páginas.
En este punto, el rastreador perfecto debería haber visitado las páginas R1, ..., Rk donde R1 es la
página con la información más importante, R2 es la siguiente más importante, y así sucesivamente.
Las páginas que van desde R1hasta Rkse llaman hot pages.

3

Crawl & Stop with Threshold: Un Asumimos de nuevo que el rastreador visita K páginas. Sin
embargo, ahora nosotros damos un punto importante G y cualquier página con I(P)3 >= G es
considerada como hot. Tomamos como valor H que representa el número de hot pages totales
que hay. P ST (C) es el porcentaje de páginas H que han sido encontradas cuando el rastreador se
para. Si K < H, entonces el rastreador ideal tendra un rendimiento de (K·100) / H. Si K >= H,
entonces el rastreador ideal tendra un 100 % de rendimiento. Un rastreador aleatorio que revisita
páginas tendra (H/T) · H hot pages cuando este pare. Asi, el rendimiento es de (K·100)/T. Sólo
si el rastreador aleatorio visita T páginas, tendra un rendimiento del 100 %.

Limited Buer Crawl : En este modelo consideramos el impacto del