Web Crawling
Coleta Automática na Web
Altigran Silva e Edleno Moura
Julho de 2002
Sumário
n
n
n
n
n
n
Algoritmo de coleta
Arquitetura
Estratégias de escalonamento
Aspectos práticos
Coleta incremental
Páginas duplicadas e Mirrors
Coleta de Páginas
n
Objetivo
n
n
Coleta automática e sistemática de
documentos da Web a serem indexados e
consultados pela máquina de busca
Coletores de Páginas
n
n
Crawlers = Spiders = Robots
Portugues: Navegadores Automáticos (??)
Coleta de Páginas
URLs Iniciais
Início
Web
Próxima URL
Coletar página
URLs a visitar
URLs visitadas
Extrair URLS
páginas
Exemplo
URL Inicial
Exemplo
Seguindo Links
Exemplo
Exemplo
Exemplo
Não serão
coletadas !!!
Seguindo Links
Arquitetura
Arquitetura Típica
Web
Requisições
HTTP
Servidor
de
Nomes (DNS)
Requisições DNS
Coletor
Coletor
Coletor
Páginas coletadas
URLs a coletar
URLs extraídas
Servidor
de
Armazenamento
Cache de Nomes
Base de Páginas
Escalonador
de
URLs
Iniciais
Novas Visitadas
Componentes
n
Coletores
n
n
n
n
Responsáveis pela requisição de páginas
aos servidores HTTP
Extraem os links das páginas recebidas e
enviam ao escalonador
Requisitam do escalonador uma ou mais
URLs a serem coletadas
Podem realizar um escalonamento local
(short term scheduling)
Componentes
n
Servidor de Armazenamento
n
n
n
Recebem as páginas ou outros objetos
coletados e armazenam em uma base
local.
Fazem a extração (parsing) de texto
Podem tratar vários formatos: Postscript,
PDF, Word, Powerpoint, etc.
Componentes
n
Servidor de Nomes
n
n
n
n
Atendem requisições DNS dos coletores
Mantêm um cache de identificadores DNS
(nomes) resolvidos
Crucial para evitar que cada coletor faça
requisições DNS remotas
Potencial ponto de gargalo
Componentes
n
Escalonador
n
n
n
Responsável por decidir qual a próxima URL a ser
coletada
Coordena as ações dos coletores
Deve garantir protocolo de exclusão
n
n
n
Retardo mínimo entre requisições a um mesmo servidor
HTTP.
Deve garantir que não haverão coletas repetidas
Potencial ponto de gargalo
Performance Típica
n
Mercator (Maio de 1999)
n
n
n
GoogleBot (Abril de 1998)
n
n
n
77.4 M requisições HTTP em 8 dias
112 docs/seg e 1.682 KB/seg
26 M requisições HTTP em 9 dias
33.5 docs/seg e 200 KB/seg
The Internet Archive crawler (Maio de 1997)
n
n
4 M HTML docs/dia
46.3 HTML docs/seg and 231 KB/seg
Mercator
n
Hardware
n
n
n
Digital Ultimate Workstation 533 MHz,
Alpha processors, 2 GB de RAM, 118 GB de
disco local
Conexão de 100 Mbit/sec FDDI
Software
n
n
Escrito Java
Procesador Java srcjava otimizado pela
Digital.
Mercator
Escalonamento
Escalonamento
n
Motivação
n
n
n
n
A Web é imensa: 10 M de servidores e bilhões
de páginas
Na prática, é impossível coletar todas as páginas
Custo de manutenção e processamento de grandes
coleções e índices é muito alto
Solução
n
Garantir que somente as melhores páginas serão
coletadas
Escalonamento
n
Em Profundidade ou LIFO
n
n
n
n
Resultada em uma coleta “focada”
Mais páginas por site
Resultados imprevisíveis
Pode-se limitar o número de níveis
Escalonamento
n
Em Largura ou FIFO
n
n
n
Produz uma coleta mais abrangente
Visita um maior número de sites
Mais usada por ser simples de implementar
Escalonamento
n
FIFO com sufixo de URL
n
n
Exemplo: *.fua.br, *.uol.com.br
Escalonamento em dois níveis:
n
n
n
n
sufixo (site)
URL
Garante cobertura balanceada entre sites
Bastante usado
Escalonamento
n
Baseadas em ranking de URLs
n
Baseada em conteúdo
n
n
Baseada em popularidade
n
n
Simples de avaliar, simples de subverter
Difícil de medir (número de acessos)
Baseada em conectividade
n
n
Número de referências (links)
“Fácil” de medir, robusto
Prioridade por conectividade
n
Referências (Backlink count)
n
n
O valor de uma página é proporcional ao número de
referências a ela
Variações:
n
n
Todos os links; links internos; links de servidores diferentes
Variações recursivas
n
Links de páginas de maior valor tem maior peso
n
Exemplo: PageRank [BP98]
Prioridade por conectividade
n
PageRank
n
Um usuário navegando aleatoriamente, seguindo
links com probabilidade uniforme d, visitaria uma
página p com probabilidade R(p)
k
d
R ( pi )
=
+
−
R ( p)
(1 d )∑
T
i = 1 C ( pi )
R( p )
C ( p)
p1... pk
T
d
PageRank de p
Fan - out de p
Páginas que apontam p
Número total de páginas
Amortizage m (d ~ 0.14)
Comparação de Estratégias
n
Experimento proposto por Cho et. al.
n
Coletar k páginas com vários tipos de
escalonamento
n
n
Critérios de avaliação
n
n
n
Randômico, FIFO, backlink e PageRank
Freqüência de termos, Backlink, PageRank, tipo de URLs
179.000 páginas do domínio stanford.edu
Resultado:
n
n
Estratégia baseada em PageRank é a melhor
Estratégia baseada em FIFO é boa
Comparação de Estratégias
n
Experimento proposto por Najork & Wiener
n
n
n
Usando somente PageRank como métrica
Resultado
n
n
328 M URLs durante 58 dias usando FIFO
Estratégia FIFO descobre páginas com alto
PageRank primeiro
Conclusão
n
Máquinas com ranking baseado em conectividade
devem coletar em FIFO
Exemplos de Escalonamento
n
AltaVista (versão inicial)
n
n
Mercator/Altavista
n
n
FIFO com exclusão por servidor
Alexa
n
n
Randômico com exclusão por servidor
Visita alternadamente conjuntos n servidores
GoogleBot
n
PageRank
Aspectos Práticos
Ética
n
Protocolo de exclusão de robôs
n
n
Recomendação informal para
desenvolvedores de robôs para a Web
Restrições de acesso
n
n
n
“robots.txt”
meta-tags especiais
Retardo mínimo entre requisições a um
mesmo servidor HTTP.
Regras de Exclusão para Sites
n
R o b o ts .tx t
n
n
n
n
n
Descreve regras de restrição para navegação
automática em um site
Encontra-se sempre na URL raiz de um servidor
Deve-se ser requisitado antes de tudo
A obediência as regras não é obrigatória
Se não forem seguidas, o administrador pode
bloquear acesso a todo conteúdo do servidor
Regras de Exclusão para Sites
Desabilita acesso a partes do site pra qualquer robô
User-agent: *
Disallow: /cgi-bin/
Disallow: /tmp/
Disallow: /private/
Desabilita acesso a todo o site para um robô específico
User-agent: Robocopo
Disallow: /
Regras de exclusão para páginas
n
n
Uso de metatags em páginas HTML
Não coletar, seguir links
n
n
Coletar, não seguir links
n
n
<meta name="ROBOTS" content="NOINDEX">
<meta name="ROBOTS" content="NOFOLLOW">
Não indexar, não seguir links
n
<meta name="ROBOTS” content="NOINDEX,NOFOLLOW">
Recomendações
n
Evitar “rapid fire”
n
n
n
Usar o header “User-Agent”
n
n
n
Usar retardo mínimo entre requisições a um
mesmo servidor HTTP
Tipicamente 60 segundos
Prover as informações necessárias para os
administradores de site
Nome do robô, e-mail, responsável, instituição,
etc.
Evitar coleta maciça em horas de tráfego alto
Restrições Práticas
n
Sites Gigantes
n
n
Limitar o número de páginas coletadas uma vez
que alguns sites contém um número
excessivamente grande páginas
Tipos de páginas
n
n
Não devem ser coletados objetos que não podem
ser indexados: .exe, .jpg, .gif, .ram, .au, …
Problemas:
n
n
Nem sempre é fácil detectar o tipo de objeto
Novos tipos aparecem todo dia
Restrições Práticas
n
Caminhos Relativos e ciclos
n
n
n
Frames e Frame Sets
Buracos Negros e Spider Traps:
n
n
<A HREF=“../../../aula/”>Coleta</A>
Links do tipo “próximo ano” em calendários
Objetos de tamanho muito grande
Coleta Incremental
Caracterização
n
Coletor periódico
n
n
Atualiza periodicamente a base de páginas
em batch
Coletor Incremenal
n
n
n
Atualiza a base de páginas de maneira
incremental e seletiva
Melhora o grau de atualidade das páginas
Descobre novas páginas mais facilmente
Caracterização
n
Objetivos
n
n
n
Atualizar as páginas já coletadas
Substituir páginas “menos imporantes”
como novas páginas mais importates.
Ideia
n
n
Fazer estimativas de quão frequente as
páginas mudam
Revisitar somente as páginas que tem
grande probalidade de mudar
Caracterização
n
Vantagens
n
n
n
Economia de banda
Melhora da autualidade da base
Incorpora novas páginas com mais rapidez
Evolução da Web
n
Experimento descrito em Cho & Garcia-Molina,
1999
n
n
n
17 a 24 de junho 1999
270 sites, 720 K páginas
Por domínos
n
n
n
n
n
com(132)
edu(78)
net/org(30)
gov(30)
Examinadas 3 K páginas de cada site diariamente
Intervalo médio de mudanças
0.35
Fração das páginas
0.30
0.25
0.20
0.15
0.10
0.05


0.00
1dia
1d-1s
1s-1m
1m-4m
>4m
Por domínio
Fração das páginas
0.6
0.5
0.4
com
netorg
edu
gov
0.3
0.2
0.1


0
1dia
1d-1s
1w-1m
1m-4m
>4m
Tempo de vida das páginas
70% vive mais de um mês
Fração de mudanças
n
1s
1s-1m 1m-4m >4m
Tempo de vida das páginas
Domínios .com são mais voláteis .edu e .gov
são mais perenes
Fração de mudanças
n
1s
1s-1m
1m-4m >4m
Tempo p/ 50% de mudança
n
Em quanto tempo a Web muda 50%?
n
Média global: 50 dias
Tempo p/ 50% de mudança
n
com:11 dias, gov: ~120 dias
Como muda a Web?
n
Baseado nos resultados experimentais
foi obtido um processo de Poisson
fT (t) = λ e-λ t
(t > 0)
no intevalor
Percentua de mundança
Como muda a Web?
Páginas que mudam
a cada 20 dias em média
Distribuição de
Poisson
Intervalo em dias
Coleta Periódica X Incremental
Períodica
Incremental
Atualizaçao Shadowing X In-Place
n
Shadowing
n
n
n
n
n
Consiste em armarmazenar as atualizações em um
espaço difrente da coleção corrente
Permite a disponibilidade da coleção corrente
Mais fácil de implementar
A coleção corrente fica obsoleta até o momento
da reconciliação
In-Place
n
n
Consideravelmente mais complicada
Garante a atualidade da coleção corrente
Frequência Fixa X Variável
n
Frequência fixa
n
n
Adotada na coleta períodica
Frequência Variável
n
Adequadata para coleta incremental com
atualizações in-place
Tratamento de Páginas
Duplicadas e Mirrors
Problema de Duplicação
n
n
Boa parte do conteúdo da Web se está
duplicado em vários sites
Os motivos são vários:
n
n
n
n
Balanceamento de carga, alta disponibilidade
Atração de tráfego (ex. Tucows)
Backup
Estimativas
n
n
Altavista, 1996 : 30% em 30 M de pags.
Google, 1997 : 36% em 26 M de pags.
Problema de Duplicação
n
Inconveniente para coleta
n
n
n
Inconveniente para processamento de
consultas
n
n
n
Esforço de coleta inútil
Espaço de armazenamento desnecessário
Maior demanda de processamento
Prejuízo na avaliação de similaridade
Inconveniente para os usuários
Duplicação de Páginas
n
n
Dadas duas URLs v ≠ u determinar se
os documentos referenciados tem o
mesmo conteúdo ou conteúdo
semelhante
Verificação exaustiva é inviável!!!
Duplicação Exata
n
n
n
n
Detecção por assinatura
Para cada URL u é calculada uma assinatura α(u)
que é armazenada
Se α(u’) = α(u) então u’ é uma duplicata de u
Message Digest 5 (MD5) (Rivest,92)
n
n
n
Gera assinaturas de 128 bits
Colisão: 1M entradas/seg. em ~600k anos
Geração eficiente
Duplicação Aproximada
n
n
Mais comum: baners, datas, etc.
Assinaturas não funcionam!
n
n
Se u’ é uma duplicata aproximada de u,
α(u’) ≠ α(u)
Solução aproximada (Broder,98)
n
n
Tomar amostras aleatórias das páginas
Gerar assinaturas das amostras
Mirrors
n
Na prática, coleções de páginas são
duplicadas
n
n
Mirrors
n
n
De 238.679 servidores com mais de 100 docs,
22.363 (9.4%) apresentam algum tipo de
duplicação (Bharat & Broder, 1998)
Sites que mantêm coleções de páginas duplicadas
de forma sistemática
Uso de assinaturas não reduz o número de
requisições feitas pelo coletor
Mirrors
LDP (Linux Doc. Project) = 25Mb, ~ 180 mirrors
Detecção de Mirrors
n
Bottom-Up
n
n
n
n
Cho, Shivakumar & Garcia-Molina, 2000
Detecção a partir do conteúdo das páginas
Construção progressiva de clusters
Top-Down
n
n
n
Bharat,Broder & Dean, 1999
Pré-filtragem baseada somente nas URLs
Testar somente os que passam na
filtragem
Bottom-up
n
Passo 1
n
Determinar pares de páginas similares com
base no conteúdo
Rid
1
1
1
2
2
Pid
10375
38950
14545
1026
18633
Bottom-up
n
Passo 2 – Estrutura de links
Link
Rid
1
1
1
2
Pid
10375
38950
14545
1026
Pid
1
1
2
2
Pid
2
3
6
10
Rid
1
1
1
2
Pid
10375
38950
14545
1026
Group by (R1.Rid, R2.Rid)
Ra = |R1|, Ls = Count(R1.Rid), Ld = Count(R2.Rid), Rb = |R2|
Bottom-Up
n
Passo 3 – Construção de clusters
S←{}
Para cada (Ra, Ls, Ld, Rb)
Se (Ra = Ls = Ld = Rb)
S ← S U {<Ra, Rb> }
Union-Find(S)
S contém pares de URLs no mesmo cluster
Bottom-up
Clusters Triviais (pares)
Expansão de Clusters
Bottom-up
Clusters Máximos
Resultados de experimento
Rank
Site
Replicas
Tamanho
1
TUCOWS WinSock utilities
http://www.tucows.com
360
1052
2
LDP Linux Doc. Project
http://sunsite.unc.edu/LDP
143
1359
3
Apache Web server
125
115
http://www.apache.org
4
JAVA 1.0.2 API
http://java.sun.com
59
552
5
Mars Pathnder
http://mars.jpl.nasa.gov
49
498
Top-Down
n
Pré-Filtragem
n
n
n
n
Não considera conteúdo das páginas
Baseada somente na estrutura extraída de
um conjunto de URLs
Algoritmos de análise de URL
Teste final baseado em similaridade de
conteúdo
Pré-Filtragem
n
Baseada em endereço IP
n
n
Determina hosts que possuem IP idênticos
ou muito similares.
Baseada nas strings das URL
n
n
Determina pares de hosts que tem URL
altamente similar.
Similaridade baseada no modelo vetorial
Pré-Filtragem
n
Baseada na conectividade dos hosts
n
n
n
Considera um hosts como um documento
único
Analisa a estrutura de ligação entre estes
pseudo-documentos.
Dois hosts são considerados mirrors se eles
apontam para conjuntos similares de hosts
Pré-Filtragem
n
Baseada nas strings da URL +
conectividade
n
Dois hosts são considerados mirrors se eles
possuem caminhos similares e documentos
na mesma posição possuem links similares
Experimentos
n
Entrada:
n
n
n
140 M URLs em 233.035 hosts com >100 URLs
Informação de conectividade
Para cada algoritmo de pré-filtragem
n
n
Determinar uma raking de 25.000 pares de host
Testar cada par sugerido usando conteúdo
Experimentos
n
Avaliação
n
n
Precisão: quais pares sugeridos são mirrors
Revocação relativa: quais pares são
sugeridos considerando todos os métodos
foram encontrados por um método em
particular
Experimentos
n
Resultados
n
n
n
Melhores métodos quanto a precisão são
os baseados em IP e prefixo de URL
Métodos individuais são limitados quanto a
revocação
Métodos combinados:
n
n
Precisão: 0.57%
Revocação: 0.86%
Artigos
n
n
n
n
The Evolution of the Web and Implications for an
Incremental Crawler, Junghoo Cho Hector GarciaMolina
Eficient Crawling Through URL Ordering, Junghoo
Cho and Hector Garcia-Molina and Lawrence Page
Breadth-First Search Crawling Yields High-Quality
Pages, Marc Najork Janet L. Wiener
Um Retrato da Web Brasileira, Veloso e outros