Rastreamento da Web e Estrutura de Links

O rastreamento da web é o processo automatizado de descoberta e download de páginas da web seguindo hiperlinks, e a estrutura de links resultante forma um grafo que os sistemas de busca tanto percorrem quanto analisam.

Definition

Rastreamento da web é a travessia algorítmica da web que começa a partir de URLs sementes e repetidamente busca páginas e extrai seus links de saída para descobrir mais páginas, enquanto a estrutura de links se refere ao grafo direcionado formado por páginas e os hiperlinks entre elas.

Scope

Este tópico aborda como os rastreadores buscam sistematicamente páginas da web e como a estrutura do grafo de hiperlinks da web é organizada. Ele trata da arquitetura do rastreador, da fronteira de URLs e das restrições de polidez, da detecção de duplicatas e quase-duplicatas, do agendamento de atualização e recrastreamento, e do respeito à exclusão de robôs. Também abrange propriedades empíricas do grafo da web, como sua ampla estrutura de gravata borboleta e distribuição de grau de cauda pesada, que informam tanto o rastreamento quanto a análise de links. Exclui o uso de links para ranqueamento, tratado em PageRank e HITS.

Core questions

• Como um rastreador descobre, prioriza e agenda as páginas que busca?
• Como a polidez, a exclusão de robôs e a carga do servidor são respeitadas durante o rastreamento?
• Como as páginas duplicadas e quase-duplicadas são detectadas e tratadas?
• Como a atualização do rastreamento é mantida à medida que as páginas mudam?
• Que estrutura em larga escala o grafo da web exibe?

Key concepts

• rastreador da web / spider
• fronteira de URLs e conjunto de sementes
• polidez de rastreamento e robots.txt
• detecção de duplicatas e quase-duplicatas
• atualização e agendamento de recrastreamento
• o grafo da web
• estrutura de gravata borboleta
• distribuições de grau de entrada e saída

Key theories

Arquitetura do rastreador e a fronteira de URLs

Um rastreador mantém uma fronteira de URLs a serem buscadas, aplica políticas de priorização e polidez, analisa páginas buscadas para extrair novos links e rastreia páginas visitadas, equilibrando cobertura, atualização e limites de recursos.

Estrutura macroscópica do grafo da web

Estudos empíricos mostram que o grafo de links da web tem uma forma característica de gravata borboleta com um grande núcleo fortemente conectado, mais componentes de entrada e saída, e grau de entrada de cauda pesada, o que restringe a alcançabilidade e informa a estratégia de rastreamento.

Clinical relevance

O rastreamento é a etapa de aquisição de dados de todo motor de busca da web e de análises da web em larga escala, arquivamento e construção de conjuntos de dados. A compreensão da estrutura de links guia o rastreamento eficiente, ajuda a estimar a cobertura e sustenta as medidas de autoridade baseadas em links usadas no ranqueamento.

History

Os rastreadores da web surgiram com a web inicial em meados da década de 1990 para alimentar índices de busca. Cho e colegas estudaram o rastreamento eficiente e a ordenação de URLs em 1998, e o estudo de 2000 'estrutura de grafo na web' revelou a macroestrutura de gravata borboleta da web. À medida que a web cresceu, o rastreamento amadureceu para uma disciplina de sistemas distribuídos em larga escala, enfatizando a atualização, cobertura e polidez.

Key figures

• Andrei Broder
• Prabhakar Raghavan
• Junghoo Cho
• Hector García-Molina

Seminal works

• broder2000
• cho1998
• manning2008

Frequently asked questions

O que é a fronteira de URLs em um rastreador?

A fronteira de URLs é a fila de URLs descobertas, mas ainda não buscadas. Um rastreador seleciona repetidamente URLs da fronteira de acordo com políticas de prioridade e polidez, busca as páginas, extrai novos links e adiciona URLs não vistas anteriormente de volta à fronteira.

O que significa a estrutura de 'gravata borboleta' da web?

Estudos em larga escala descobriram que o grafo da web tem um grande núcleo fortemente conectado, um componente 'de entrada' de páginas que podem alcançar o núcleo, um componente 'de saída' alcançável a partir dele, além de tentáculos e partes desconectadas, assemelhando-se a uma gravata borboleta. Essa forma afeta quais páginas um rastreador pode alcançar a partir de sementes dadas.