¿Qué hace un rastreador web?

Toda la información

Política de Arrastre o Rastreo

El comportamiento de un buscador web es el resultado de una combinación de políticas:

una política de selección que establece las páginas de descarga,
una política de revisita que establece cuándo debe buscar cambios en las páginas,
una política de cortesía que indica cómo evitar la sobrecarga de los sitios Web , y
una política de paralelización que indica la forma de coordinar los rastreadores web distribuidos

Política de selección

Teniendo en cuenta el tamaño actual de la Web, incluso los grandes motores de búsqueda cubren sólo una porción de la parte a disposición del público. Un estudio de 2009 mostró incluso a gran escala de los motores de búsqueda índice de no más de 40-70% de la Web indexable; un estudio previo realizado por Steve Lawrence y Lee Giles mostró que ningún motor de búsqueda indexa más de un 16% de la Web en 1999. Como rastreador siempre se descarga sólo una fracción de las páginas web, es altamente deseable para la fracción descargado poder contener las páginas más relevantes y no sólo una muestra aleatoria de la web.

Esto requiere una métrica de importancia para la priorización de las páginas Web. La importancia de una página es una función de su calidad intrínseca, su popularidad en términos de enlaces o visitas, e incluso de su URL (este último es el caso de los motores verticales de búsqueda restringidos a un único dominio de nivel superior, o motores de búsqueda restringidas a un sitio web fija). El diseño de una buena política de selección tiene una dificultad añadida: tiene que trabajar con información parcial, ya que el conjunto completo de páginas web no se conoce durante el rastreo.

Junghoo Cho et al. hicieron el primer estudio sobre las políticas para el rastreo de programación. Su conjunto de datos estaba a 180.000 páginas se arrastran desde el stanford.edu de dominio, en el que una simulación de rastreo se realizó con diferentes estrategias. Las métricas de pedido probados fueron primero en amplitud, vínculo de retroceso recuento y parciales cálculos Pagerank. Una de las conclusiones fue que si el rastreador quiere descargar páginas con alto Pagerank temprana durante el proceso de rastreo, entonces la estrategia Pagerank parcial es la mejor, seguida de primero en amplitud y vínculo de retroceso de recuento. Sin embargo, estos resultados son para un solo dominio. Cho también escribió su Ph.D. tesis doctoral en Stanford en el rastreo web.

Najork y Wiener realizaron un rastreo de 328 millones de páginas, utilizando una búsqueda de anchura.⁵ Descubrieron que un rastreo de búsqueda de anchura captura las páginas con alto Pagerank al principio del rastreo (pero no compararon esta estrategia con otras). La explicación que dan los autores para este resultado es que «las páginas más importantes tienen muchos enlaces hacia ellas desde numerosos hosts, y esos enlaces se encontrarán pronto, independientemente de en qué host o página se origine el rastreo».

Abiteboul diseñó una estrategia de rastreo basada en un algoritmo llamado OPIC (On-line Page Importance Computation). En el OPIC, cada página recibe una suma inicial de «dinero» que se distribuye por igual entre las páginas a las que apunta. Es similar al cálculo del PageRank, pero es más rápido y sólo se realiza en un paso. Un rastreador impulsado por OPIC descarga primero las páginas de la frontera de rastreo con mayores cantidades de «efectivo». Los experimentos se llevaron a cabo en un gráfico sintético de 100.000 páginas con una distribución de ley potencial de los enlaces internos. Sin embargo, no hubo comparación con otras estrategias ni experimentos en la web real.

Baeza-Yates et al. utilizaron la simulación en dos subconjuntos de la web de 3 millones de páginas del dominio .gr y .cl, probando varias estrategias de rastreo. Demostraron que tanto la estrategia OPIC como una estrategia que utiliza la longitud de las colas por sitio son mejores que el rastreo búsqueda de anchura, y que también es muy eficaz utilizar un rastreo anterior, cuando está disponible, para guiar el actual.

Daneshpajouh et al. diseñaron un algoritmo basado en la comunidad para descubrir buenas semillas. Su método rastrea páginas web con alto PageRank de diferentes comunidades en menos iteraciones en comparación con el rastreo que parte de semillas aleatorias. Uno puede extraer buenas semillas de un gráfico web previamente rastreado utilizando este nuevo método. Usando estas semillas, un nuevo rastreo puede ser muy efectivo.

Restringir los siguientes enlaces

Un rastreador puede querer buscar sólo páginas HTML y evitar todos los demás tipos MIME. Para solicitar sólo recursos HTML, un rastreador puede hacer una petición HTTP HEAD para determinar el tipo MIME de un recurso web antes de solicitar el recurso completo con una petición GET. Para evitar realizar numerosas peticiones HEAD, un rastreador puede examinar la URL y sólo solicitar un recurso si la URL termina con ciertos caracteres como .html, .htm, .asp, .aspx, .php, .jsp, .jspx o una barra (/). Esta estrategia puede hacer que se omitan involuntariamente numerosos recursos web HTML.

Algunos rastreadores también pueden evitar solicitar cualquier recurso que tenga un «?» (se producen dinámicamente) para evitar las trampas de arañas que pueden hacer que el rastreador descargue un número infinito de URL de un sitio web. Esta estrategia no es fiable si el sitio utiliza la reescritura de URLs para simplificarlas.

Normalización de URLs

Tipos de normalizaciones URI

Los rastreadores suelen realizar algún tipo de normalizaciones de URL para evitar rastrear el mismo recurso más de una vez. El término normalización de URL, también llamado canonización de URL, se refiere al proceso de modificación y normalización de una URL de manera consistente. Hay varios tipos de normalización que pueden realizarse, incluyendo la conversión de las URLs a minúsculas, la eliminación de los segmentos «.» y «..», y la adición de barras (/) al final del componente de la ruta no vacía.⁹

Rastreo de rutas

Algunos rastreadores pretenden descargar/cargar tantos recursos como sea posible de un sitio web concreto. Para ello, se introdujo el rastreo ascendente, que asciende a todas las rutas de cada URL que pretende rastrear. Por ejemplo, cuando se le da una URL inicial como http://llama.org/hamster/monkey/page.html, intentará rastrear /hamster/monkey/, /hamster/ y /. Cothey descubrió que un rastreador ascendente era muy eficaz para encontrar recursos aislados, o recursos para los que no se habría encontrado ningún enlace entrante en un rastreo normal.

Rastreo focalizado[editar]

La importancia de una página para un rastreador también puede expresarse en función de la similitud de una página con una consulta determinada. Los rastreadores web que intentan descargar páginas similares entre sí se denominan rastreadores enfocados o rastreadores tópicos. Los conceptos de rastreo tópico y enfocado fueron introducidos por primera vez por Filippo Menczer y por Soumen Chakrabarti et al.

El principal problema del rastreo enfocado es que, en el contexto de un rastreador web, nos gustaría poder predecir la similitud del texto de una página determinada con la consulta antes de descargar la página. Un posible predictor es el texto ancla de los enlaces; éste fue el enfoque adoptado por Pinkerton en el primer rastreador web de los primeros días de la Web. Diligenti et al. proponen utilizar el contenido completo de las páginas ya visitadas para inferir la similitud entre la consulta de conducción y las páginas que aún no han sido visitadas. El rendimiento de un rastreo enfocado depende sobre todo de la riqueza de los enlaces en el tema específico que se busca, y un rastreo enfocado suele depender de un motor de búsqueda web general para proporcionar puntos de partida.

Rastreador centrado en el ámbito académico

Un ejemplo de los rastreadores focalizados son los rastreadores académicos, que rastrean documentos académicos de libre acceso, como el citeseerxbot, que es el rastreador del motor de búsqueda CiteSeerX. Otros motores de búsqueda académica son Google Scholar y Microsoft Academic Search, etc. Dado que la mayoría de los documentos académicos se publican en formato PDF, este tipo de rastreador está especialmente interesado en rastrear archivos PDF, PostScript y Microsoft Word, incluidos sus formatos comprimidos. Por ello, los rastreadores generales de código abierto, como Heritrix, deben personalizarse para filtrar otros tipos de MIME, o bien se utiliza un middleware (lógica de intercambio de información entre aplicaciones) para extraer estos documentos e importarlos a la base de datos y al repositorio de rastreo enfocado. Identificar si estos documentos son académicos o no es un reto y puede añadir una sobrecarga significativa al proceso de rastreo, por lo que se realiza como un proceso posterior al rastreo utilizando algoritmos de aprendizaje automático o de expresión regular. Estos documentos académicos suelen obtenerse de las páginas de inicio de las facultades y estudiantes o de páginas de publicaciones de los institutos de investigación. Dado que los documentos académicos representan sólo una pequeña fracción de las páginas web, es importante una buena selección de semillas para aumentar la eficacia de estos rastreadores web.¹⁷ Otros rastreadores académicos pueden descargar archivos de texto plano y HTML que contienen metadatos de artículos académicos, como títulos, artículos y resúmenes. Esto aumenta el número total de artículos, pero una parte importante puede no ofrecer descargas gratuitas en PDF.

Rastreador enfocado en la semántica

Otro tipo de rastreadores enfocados es el rastreador enfocado en la semántica, que hace uso de ontologías de dominios para representar mapas tópicos y enlazar páginas web con conceptos ontológicos relevantes para la selección y categorización. Además, las ontologías pueden actualizarse automáticamente en el proceso de rastreo. Dong et al. introdujeron un rastreador basado en el aprendizaje de ontologías que utiliza una máquina de vectores de apoyo para actualizar el contenido de los conceptos ontológicos cuando se rastrean las páginas web.

Política de revisitas

La web tiene una naturaleza muy dinámica, y rastrear una fracción de la web puede llevar semanas o meses. Para cuando un rastreador de la web ha terminado su rastreo, pueden haber ocurrido muchos eventos, incluyendo creaciones, actualizaciones y eliminaciones.

Desde el punto de vista del motor de búsqueda, existe un coste asociado a la no detección de un evento y, por tanto, a tener una copia obsoleta de un recurso. Las funciones de coste más utilizadas son la novedad y la antigüedad.

Novedad: Es una medida binaria que indica si la copia local es exacta o no. La novedad de una página p en el repositorio a tiempo t se define como:

F_{p}(t)={\begin{cases}1&{\rm {si}}~p~{\rm {~es~igual~a~la~copia~local~a~tiempo}}~t\\0&{\rm {de~lo~contrario}}\end{cases}}

Antigüedad: Es una medida que indica la antigüedad de la copia local. La antigüedad de una página p en el repositorio a tiempo t se define como:

A_{p}(t)={\begin{cases}0&{\rm {si}}~p~{\rm {~no~es~modificado~a~tiempo}}~t\\t-{\rm {tiempo~de~modificacion~de}}~p&{\rm {de~lo~contrario}}\end{cases}}

Coffman et al. trabajaron con una definición del objetivo de un rastreador web que es equivalente a la novedad, pero utilizan una redacción diferente: proponen que un rastreador debe minimizar la fracción de tiempo que las páginas permanecen obsoletas. También señalaron que el problema del rastreo de la web puede modelarse como un sistema de sondeo de cola múltiple y servidor único, en el que el rastreador de la web es el servidor y los sitios web son las colas. Las modificaciones de las páginas son la llegada de los clientes, y los tiempos de espera son el intervalo entre los accesos a las páginas de un mismo sitio web. Según este modelo, el tiempo medio de espera de un cliente en el sistema de sondeo equivale a la edad media del rastreador web.

El objetivo del rastreador es mantener en su colección la novedad de las páginas lo más alta posible, o mantener la antigüedad de las páginas lo más baja posible. Estos objetivos no son equivalentes: en el primer caso, el rastreador sólo se preocupa de cuántas páginas están desactualizadas, mientras que en el segundo caso, el rastreador se preocupa de la antigüedad de las copias locales de las páginas.

Cho y García-Molina estudiaron dos políticas simples de revisita:

Política uniforme: Consiste en volver a visitar todas las páginas de la colección con la misma frecuencia, independientemente de sus tasas de cambio.
Política proporcional: Consiste en volver a visitar con más frecuencia las páginas que cambian con más frecuencia. La frecuencia de visita es directamente proporcional a la frecuencia de cambio (estimada).

En ambos casos, el orden de rastreo repetido de las páginas puede hacerse de forma aleatoria o fija.

Cho y García-Molina demostraron el sorprendente resultado de que, en términos de novedad, la política uniforme supera a la política proporcional tanto en una web simulada como en un rastreo real. Intuitivamente, el razonamiento es que, como los rastreadores web tienen un límite en cuanto al número de páginas que pueden rastrear en un plazo determinado, (1) asignarán demasiados rastreos nuevos a las páginas que cambian rápidamente a expensas de las páginas que se actualizan con menos frecuencia, y (2) la frescura de las páginas que cambian rápidamente dura menos que la de las que cambian con menos frecuencia. En otras palabras, una política proporcional asigna más recursos al rastreo de las páginas que se actualizan con frecuencia, pero experimenta menos tiempo de novedad general de las mismas.

Para mejorar la novedad, el rastreador debe penalizar los elementos que cambian con demasiada frecuencia. La política de revisita óptima no es ni la política uniforme ni la política proporcional. El método óptimo para mantener una novedad media alta incluye ignorar las páginas que cambian con demasiada frecuencia, y lo óptimo para mantener una antigüedad media baja es utilizar frecuencias de acceso que aumenten monótonamente (y de forma sublineal) con la tasa de cambio de cada página. En ambos casos, lo óptimo está más cerca de la política uniforme que de la proporcional: como señalan Coffman et al., «para minimizar el tiempo de obsolescencia esperado, los accesos a cualquier página particular deben mantenerse lo más uniformemente espaciados posible«. Las fórmulas explícitas para la política de revisita no son alcanzables en general, pero se obtienen numéricamente, ya que dependen de la distribución de los cambios de página. Cho y García-Molina muestran que la distribución exponencial es un buen ajuste para describir los cambios de página, mientras que Ipeirotis et al. muestran cómo utilizar herramientas estadísticas para descubrir los parámetros que afectan a esta distribución, hay que tener en cuenta que las políticas de revisita observadas aquí consideran que todas las páginas son homogéneas en términos de calidad («todas las páginas de la web valen lo mismo»), algo que no es un escenario realista, por lo que debería incluirse más información sobre la calidad de la página web para lograr una mejor política de rastreo.

Política de cortesía

Los rastreadores pueden recuperar los datos mucho más rápido y con mayor profundidad que los humanos, por lo que pueden tener un impacto devastador en el rendimiento de un sitio. Si un solo rastreador realiza varias peticiones por segundo y/o descarga archivos de gran tamaño, un servidor puede tener dificultades para atender las peticiones de varios rastreadores.

Como señala Koster, el uso de rastreadores web es útil para una serie de tareas, pero tiene un precio para la comunidad en general. Los costes de usar rastreadores web incluyen:

Recursos de red, ya que los rastreadores requieren un ancho de banda considerable y funcionan con un alto grado de paralelismo durante un periodo largo de tiempo;
la sobrecarga de los servidores, especialmente si la frecuencia de los accesos a un determinado servidor es demasiado elevada;
rastreadores mal escritos, al poder colapsar servidores o routers, o que descargan páginas que no pueden manejar; y
rastreadores personales que, si son desplegados por demasiados usuarios, pueden alterar las redes y los servidores web.

Una solución parcial a estos problemas es el estándar de exclusión de robots, también conocido como protocolo robots.txt. Se trata de un estándar para que los administradores indiquen a qué partes de sus servidores web no deben acceder los rastreadores. Este estándar no incluye una sugerencia para el intervalo de visitas al mismo servidor, aunque este intervalo es la forma más eficaz de evitar la sobrecarga del servidor. Los motores de búsqueda comerciales, como Google, Ask Jeeves, MSN y Yahoo! Search, pueden utilizar un parámetro adicional «Retraso de rastreo»: un parámetro en el archivo robots.txt para indicar el número de segundos de retraso entre peticiones.

El primer intervalo propuesto entre las sucesivas cargas de páginas fue de 60 segundos. Sin embargo, si las páginas se descargaran a este ritmo desde un sitio web con más de 100.000 páginas a través de una conexión perfecta con latencia cero y ancho de banda infinito, se tardaría más de 2 meses en descargar sólo ese sitio web completo; además, sólo se utilizaría una fracción de los recursos de ese servidor web.

Cho utiliza 10 segundos como intervalo para los accesos, y el rastreador WIRE utiliza 15 segundos por defecto. El rastreador MercatorWeb sigue una política de cortesía adaptativa: si ha tardado t segundos en descargar un documento de un servidor determinado, el rastreador espera 10t segundos antes de descargar la siguiente página. Dill et al. utilizan 1 segundo.

Para quienes utilizan rastreadores web con fines de investigación, es necesario un análisis más detallado respecto a la relación coste-beneficio y se debe tener en cuenta consideraciones éticas a la hora de decidir dónde rastrear y a qué velocidad hacerlo.

Las pruebas anecdóticas de los registros de entrada muestran que los intervalos de acceso de los rastreadores conocidos varían entre 20 segundos y 3-4 minutos. Cabe destacar que, incluso siendo muy educados y tomando todas las precauciones para evitar la sobrecarga de los servidores web, se reciben algunas quejas de los administradores de servidores web. Brin y Page señalan que: «… ejecutar un rastreador que se conecta a más de medio millón de servidores (…) genera una buena cantidad de correos electrónicos y llamadas telefónicas. Debido al gran número de personas que se conectan, siempre hay quienes no saben lo que es un rastreador, porque es el primero que ven».

Política de paralelización

Un rastreador paralelo es un rastreador que ejecuta múltiples procesos en paralelo. El objetivo es maximizar la tasa de descarga minimizando la sobrecarga de la paralización y evitar descargas repetidas de la misma página. Para evitar descargar la misma página más de una vez, el sistema de rastreo requiere una política de asignación de las nuevas URLs descubiertas durante el proceso de rastreo, ya que la misma URL puede ser encontrada por dos procesos de rastreo diferentes.