El comportamiento de un rastreador web es el resultado de una combinación de políticas:
- una política de selección que establece las páginas a descargar,
- una política de re-visita que establece cuándo comprobar los cambios en las páginas,
- una política de cortesía que establece cómo evitar la sobrecarga de los sitios web.
- una política de paralelización que establece cómo coordinar rastreadores web distribuidos.
- Política uniforme: Esto implica 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).
- recursos de red, ya que los rastreadores requieren un ancho de banda considerable y operan con un alto grado de paralelismo durante un largo periodo de tiempo;
- sobrecarga del servidor, especialmente si la frecuencia de accesos a un determinado servidor es demasiado alta;
- rastreadores mal escritos, que pueden colapsar servidores o routers, o que descargan páginas que no pueden manejar; y
- rastreadores personales que, si son desplegados por demasiados usuarios, pueden perturbar las redes y los servidores web.
Política de selecciónEditar
Dado el tamaño actual de la Web, incluso los grandes motores de búsqueda cubren sólo una parte de la parte disponible públicamente. Un estudio de 2009 mostró que incluso los motores de búsqueda a gran escala no indexan más del 40-70% de la Web indexable; un estudio anterior de Steve Lawrence y Lee Giles mostró que ningún motor de búsqueda indexaba más del 16% de la Web en 1999. Como un rastreador siempre descarga sólo una fracción de las páginas web, es muy deseable que la fracción descargada contenga las páginas más relevantes y no sólo una muestra aleatoria de la web.
Esto requiere una métrica de importancia para priorizar las páginas web. La importancia de una página es función de su calidad intrínseca, de su popularidad en términos de enlaces o visitas, e incluso de su URL (este último es el caso de los buscadores verticales restringidos a un único dominio de primer nivel, o de los buscadores restringidos a un sitio web fijo). El diseño de una buena política de selección tiene una dificultad añadida: debe trabajar con información parcial, ya que durante el rastreo no se conoce el conjunto completo de páginas web.
Junghoo Cho et al. realizaron el primer estudio sobre políticas de programación del rastreo. Su conjunto de datos fue un rastreo de 180.000 páginas del dominio stanford.edu, en el que se realizó una simulación de rastreo con diferentes estrategias. Las métricas de ordenación probadas fueron breadth-first, recuento de backlinks y cálculos parciales de PageRank. Una de las conclusiones fue que si el rastreador quiere descargar páginas con alto Pagerank al principio del proceso de rastreo, la estrategia de Pagerank parcial es la mejor, seguida de breadth-first y backlink-count. Sin embargo, estos resultados son para un solo dominio. Cho también escribió su tesis doctoral en Stanford sobre el rastreo de la web.
Najork y Wiener realizaron un rastreo real de 328 millones de páginas, utilizando la ordenación breadth-first. Descubrieron que un rastreo breadth-first captura 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 del host o la página en la que se origine el rastreo»
Abiteboul diseñó una estrategia de rastreo basada en un algoritmo llamado OPIC (On-line Page Importance Computation). En 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 se realiza en un solo 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 power-law de los enlaces internos. Sin embargo, no hubo comparación con otras estrategias ni experimentos en la Web real.
Boldi et al. utilizaron la simulación en subconjuntos de la Web de 40 millones de páginas del dominio .it y 100 millones de páginas del rastreo de WebBase, probando breadth-first frente a depth-first, ordenación aleatoria y una estrategia omnisciente. La comparación se basó en la medida en que el PageRank calculado en un rastreo parcial se aproxima al verdadero valor del PageRank. Sorprendentemente, algunas visitas que acumulan PageRank muy rápidamente (sobre todo, breadth-first y la visita omnisciente) proporcionan aproximaciones progresivas muy pobres.
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 breadth-first, 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 comienza con semillas aleatorias. Con este nuevo método se pueden extraer buenas semillas de un gráfico web previamente rastreado. Usando estas semillas, un nuevo crawl puede ser muy efectivo.
Restringiendo los enlaces seguidosEditar
Un crawler 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 contenga un «?» (se produce dinámicamente) para evitar las trampas para 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 simplificar sus URLs.
Normalización de URLsEditar
Los rastreadores suelen realizar algún tipo de normalización 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 se pueden realizar, incluyendo la conversión de las URL 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 ruta ascendenteEditar
Algunos rastreadores tienen la intención de descargar/cargar tantos recursos como sea posible de un sitio web en particular. Así que se introdujo el crawler path-ascending que ascendería a cada ruta en cada URL que pretende rastrear. Por ejemplo, cuando se le da una URL semilla de http://llama.org/hamster/monkey/page.html, intentará rastrear /hamster/monkey/, /hamster/, y /. Cothey descubrió que un rastreador ascendente por rutas era muy eficaz para encontrar recursos aislados, o recursos para los que no se habría encontrado ningún enlace entrante en un rastreo regular.
Rastreo enfocadoEditar
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 que son 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 ser capaces de predecir la similitud del texto de una página dada con la consulta antes de descargar realmente 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 basarse en un motor de búsqueda web general para proporcionar puntos de partida.
Rastreador enfocado en el ámbito académicoEditar
Un ejemplo de los rastreadores enfocados son los rastreadores académicos, que rastrean documentos relacionados con el ámbito académico 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 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 esto se realiza como un proceso posterior al rastreo utilizando aprendizaje automático o algoritmos de expresión regular. Estos documentos académicos suelen obtenerse de las páginas de inicio de las facultades y los estudiantes o de las páginas de publicación de los institutos de investigación. Dado que los documentos académicos representan sólo una pequeña parte de las páginas web, una buena selección de semillas es importante para aumentar la eficacia de estos rastreadores web. Otros rastreadores académicos pueden descargar archivos de texto plano y HTML, que contienen metadatos de documentos académicos, como títulos, artículos y resúmenes. Esto aumenta el número total de documentos, pero una fracción significativa puede no proporcionar descargas gratuitas en PDF.
Rastreo enfocado semánticoEditar
Otro tipo de rastreadores enfocados es el rastreador enfocado semántico, que hace uso de ontologías de dominio 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 al rastrear las páginas web.
Política de revisiónEditar
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 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, hay un coste asociado a no detectar un evento, y por tanto tener una copia obsoleta de un recurso. Las funciones de coste más utilizadas son la frescura y la antigüedad.
Frescura: Es una medida binaria que indica si la copia local es precisa o no. La frescura de una página p en el repositorio en el momento t se define como:
F p ( t ) = { 1 si p es q u a l a c o p i a a l a t i m e n t o 0 o t r a s p a g a n d a s {\displaystyle F_{p}(t)={begin{cases}1&{\rm {if}}~p~{\rm {~is~equal~to~the~local~copy~at~time}}~t\\0&{\rm {otherwise}}\end{cases}}}
Age: Es una medida que indica la antigüedad de la copia local. La edad de una página p en el repositorio, en el momento t se define como:
A p ( t ) = { 0 si p no está m o d i f i c a d a e n e l t i e m p o – m o d i f i c a d o e n e l t i e m p o i s e {\displaystyle A_{p}(t)={begin{cases}0& {{rm {if}~p~{rm {~no~se~modifica~a~tiempo}} {t\t-{\rm {modificación~tiempo~de}~p&{rm}{si no}{fin}{caso}}
Coffman et al. trabajaron con una definición del objetivo de un rastreador web que es equivalente a la frescura, 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 es equivalente a la edad media del rastreador web.
El objetivo del rastreador es mantener la frescura media de las páginas en su colección lo más alta posible, o mantener la edad media 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.
Dos políticas simples de re-visita fueron estudiadas por Cho y García-Molina:
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 frescura media, la política uniforme supera a la política proporcional tanto en una Web simulada como en un rastreo real de la Web. 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 periodo de tiempo 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 frescura general de las mismas.
Para mejorar la frescura, el rastreador debe penalizar los elementos que cambian con demasiada frecuencia. La política de re-visita óptima no es ni la política uniforme ni la política proporcional. El método óptimo para mantener la frescura media alta incluye ignorar las páginas que cambian demasiado a menudo, y el óptimo para mantener la edad media baja es utilizar frecuencias de acceso que aumenten monotónicamente (y de forma sub-lineal) con la tasa de cambio de cada página. En ambos casos, el óptimo está más cerca de la política uniforme que de la política 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 re-visita 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 demuestran 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 re-visita consideradas 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 se debería incluir más información sobre la calidad de la página web para lograr una mejor política de rastreo.
Política de cortesíaEditar
Los rastreadores pueden recuperar datos mucho más rápido y en mayor profundidad que los buscadores humanos, por lo que pueden tener un impacto agobiante en el rendimiento de un sitio. Si un solo rastreador realiza múltiples peticiones por segundo y/o descarga archivos de gran tamaño, un servidor puede tener dificultades para mantener el ritmo de 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 del uso de rastreadores web incluyen:
Una solución parcial a estos problemas es el protocolo de exclusión de robots, también conocido como protocolo robots.txt que es 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 sobre el intervalo de visitas a un mismo servidor, a pesar de que este intervalo es la forma más eficaz de evitar la sobrecarga del servidor. Recientemente, los motores de búsqueda comerciales como Google, Ask Jeeves, MSN y Yahoo! Search pueden utilizar un parámetro adicional «Crawl-delay:» en el archivo robots.txt para indicar el número de segundos que se debe retrasar entre las solicitudes.
El primer intervalo propuesto entre las sucesivas cargas de páginas era de 60 segundos. Sin embargo, si se descargaran páginas a este ritmo de 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. Esto no parece aceptable.
Cho utiliza 10 segundos como intervalo para los accesos, y el crawler WIRE utiliza 15 segundos por defecto. El crawler MercatorWeb sigue una política de cortesía adaptativa: si se tardó t segundos en descargar un documento de un determinado servidor, el crawler 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 de la relación coste-beneficio y se deben tener en cuenta consideraciones éticas a la hora de decidir dónde rastrear y a qué velocidad hacerlo.
Los datos anecdóticos de los registros de acceso 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 a la gran cantidad de personas que se conectan, siempre hay quienes no saben lo que es un crawler, porque es el primero que han visto.»
Política de paralelizaciónEditar
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.