Engenhos de Busca Web
Equipe: Cássio Melo, Alexandre Barza, Manuela
Nascimento e Rodrigo Freitas
{cam2, ab, mcn, rqf}
Jul/2007
Roteiro
 Evolução e Desafios;
 Arquitetura;
 Rankeamento;
 Authorities, Hubs, Hits, PageRank e Hilltop;
 Spiders;
 Estratégias de Busca;
 Indexação;
 Browsing;
 Metabuscas;
 Conclusão.
Evolução Web
 Gigantesco e ubíquo banco de dados, sem
estrutura definida.
 Como se comunicar ?
Evolução Web
 1990 - Tim Berners-Lee do CERN(Conseil Européen
pour la Recherche Nucleaire) cria o WWW;
 Libwww, Erwise, Voilawww, Mosaic(NCSA), etc...
Evolução Web
 Em 1993, havia aproximadamente 50 sites;
 Netcraft Survey - 108,810,358 (fevereiro de 2007).
Aumento de 2.000.000 % em 14 anos.
"The good thing about digital media is that you can save
everything.
The bad thing about digital media is that you can lose
everything."
Desafios
Dados:
 Descentralização;
 Volatilidade;
 Volume;
 Redundancia;
 Qualidade - The cult of the amateur is digital utopianism’s
most seductive delusion… It suggests, mistakenly, that everyone
has something interesting to say.
Desafios
Pessoas:
 Especificar Consulta.
 Interpretar a resposta.
 Objetivo:
Respostas relevantes para cada consulta.
Arquiteturas
 Sistemas RI padrão + WEB
 Principais arquiteturas
 Arquitetura centralizada
 Arquitetura distribuída
Arquitetura Centralizada
Web
Indexer
Index
Query Engine
Arquitetura Centralizada
Arquitetura Centralizada
 Principais problemas:
 Sobrecarga dos servidores
 Aumento de tráfego (spiders)
 Informação recolhida sem coordenação
Arquitetura Distribuida
Authorities
 Definição: são páginas que são reconhecidas por
proverem informações significantes, confiáveis e úteis
sobre um determinado tópico
 Busca informação desejada dentro dos sites
Authorities
 Authorities for query: “Java”
 java.sun.com
 comp.lang.java FAQ
 Authorities for query “search engine”




Yahoo.com
Excite.com
Lycos.com
Altavista.com
 Authorities for query “Gates”
 Microsoft.com
 roadahead.com
Hubs
 Definição: termo para o grupo que une todos os sites
web que recebem grande quantidade de links e que
por sua vez fazem laço com páginas web que
consideram importantes.
 Ou seja, são páginas de índices que provêem grande
quantidade de links úteis para páginas de conteúdo
relevante
Authorities e Hubs
 Na definição de Jon Kleinberg, de hubs e autoridades:
uma boa autoridade será uma página apontada por
bons hubs e um bom hub será uma página que aponta
para boas
autoridades.
HITS (Hyperlink Induced Topic Search)
 Tenta determinar hubs e autoridades em um
tópico particular através da análise de um grafo
relevante da web
 É baseado em fatos recursivos pois hubs apontam
para autoridades e autoridades são apontadas por
hubs.
 O peso de cada link dependerá dos índices hub e
authority da página em que se encontra. O
processo de cálculo é recursivo e pode envolver
bilhões de páginas. Quando de sua concepção, o
algoritmo mostrou-se impraticável.
Construindo um subgrafo
 Hubs apontam para muitas autoridades.
 Autoridades são apontadas por muitos hubs.
Hubs
Authorities
PageRank
 Atribui um peso para cada elemento “hiperlincado”.
Os links são como votos.
 Quanto mais apontamentos a página tiver, maior vai
ser o page rank dela.
PageRank
 Medida de importância de uma página para o Google.
 Download da barra de ferramentas do Google.
Page Rank
PageRank
 Falhas:
 Qualquer página contida no índice, aumentava o
PageRank da página que recebia o link.
 Webmasters estavam comprando links, para aumentar
seu pagenRank
 E uma vez tendo contruído um site de alto pagerank,
ficava fácil para os webmasters construírem outros
sitese, de imediato, apontar links de suas próprias
páginas e conseguir um bom posicionamento inicial.
Solução: Algoritmo Hilltop
Algoritmo Hilltop
 O Hilltop procura detectar hosts afiliados; se um link
apontar para uma página em um host afiliado, o valor
do link é descontado.
 Hosts afiliados = mesmos primeiros três octetos de
endereço IP
 Ex.: Hosts com IPs 200.109.112.132 e 200.109.112.132 (ou
qualquer outro host de IP 200.109.112.xxx) são
considerados afiliados
Algoritmo Hilltop
 O hilltop deixa claro que se eu quiser ter bom
posicionamento do meu site de filmes é muito melhor
eu ter um link em mdb.com (um expert no tópico
filmes) do que um link em nature.com
Spiders (Robots/Bots/Crawlers)
 Procuram informações nos sites
 Entram nas páginas e lêem o conteúdo assim como os
internautas.
 Não avaliam o site propriamente.
 Avaliam o código que o gera.
 O código deve estar em perfeita sintonia com os
critérios que esses programas utilizam.
24
Spiders
(Robots/Bots/Crawlers)
 Alguns desses critérios:
 Indexação
 Banco de dados é criado para cada termo de busca e são
relacionadas as paginas
 Quando se faz a busca, a spider recorre a esse banco de dados.
 Html- as ferramentas de buscam entendem melhor.
 Links- Quanto mais sites tiverem links para a página,
mais relevante será essa página.
25
Estratégias de Busca
Busca em Largura
26
Estratégias de Busca
Busca em Profundidade
27
Prós e Contras…
 Busca em largura requer muita memória para guardar
todos os nós do nível anterior
 porém é o método padrão utilizado.
 Busca em profundidade necessita de menos memória
 porém pode se “perder” em um único nó, dada a alta
conectividade da Web.
28
Spider Multi-tarefa
 Fazer o download de páginas é o “Gargalo” dos
engenhos de busca
 Melhor ter múltiplas “threads” rodando em
hosts diferentes
 Maximizar a distribuição das URL’s para aumentar o
“through-put” e evitar sobrecarregar um servidor.
 Primeiros spiders do Google tinham cerca de 300
threads cada, e juntos podiam fazer o download de
cerca de 100 páginas por segundo
29
Directed/Focused Spidering
 Selecionam as páginas mais “interessantes” primeiro.
 Direcionado aos Links
30
Spidering direcionado ao Link
 Monitora links e verifica o in-degree e out-degree de
cada página encontrada.
31
Spidering direcionado ao Link
 Busca na fila primeiramente páginas populares que
são apontadas por muitos links (authorities).
 Busca na fila primeiramente páginas “sumário”com
muitos links (hubs).
32
Indexação
Análise
 Análise do Formato
 Reconhecimento de Linguagem
 Processamento de Linguagem Natural
 Eliminação de stopwords
 Operações de normalização

Pontuação, espaços, uppercase,...
 Tokenization
 Reconhecimento da Seção
 Indexação de Meta Tag
34
Indexação
 A maioria dos sistemas web usam variantes do
arquivo invertido
 Lista de palavras ordenadas com um conjunto de
ponteiros para as páginas em que elas ocorrem
 Armazenamento da descrição de cada webpage
35
Busca no Arquivo de Índices
 Consulta é respondida através de busca binária no
arquivo de índices
 Consulta formada por várias palavras
 o sistema recupera os índices para cada palavra isolada
 os resultados da recuperação são combinados para
gerar a resposta final
36
Busca no Arquivo de Índices
 Arquivos de índices invertidos também podem
armazenar as ocorrências das palavras nos
documentos (full inversion)
 Maior custo de armazenagem
 Possibilidade de consultas por frases e expressões
através da proximidade das palavras no documento
37
Busca no Arquivo de Índices
 Para encontrar palavras que iniciam com um dado
prefixo, é necessário fazer duas buscas binárias na
lista de palavras ordenadas
 Ex.: auto-análise
 Buscas mais complexas, como palavras com erro,
requerem um tempo considerável de
processamento
 Por causa do tamanho do vocabulário
38
Browsing
 Diretórios Web
 Pequena cobertura

geralmente menos de 1% das páginas
 Links geralmente possuem conteúdos mais relevantes
 Alguns são focados em um domínio específico
 Muitas ferramentas de busca são híbridas
 Exemplo: Yahoo!
39
Browsing
 Diretórios Web
 Vantagens


Documentos mais relevantes
Possibilidade de armazenar o conteúdo de todas as
páginas classificadas, por serem em menores
quantidades
 Desvantagens
 Nem todos os documentos são classificados
 Documentos mudam constantemente
 Tentativas de classificação automática não são 100%
efetivas
40
Metabuscas
 Servidores Web que enviam uma consulta a vários
motores de busca, diretórios Web e outros bancos
de dados
 Coletam as respostas e unificam o resultado
 Vantagens
 Habilidade em unificar resultados de várias origens
 Utilização de uma interface única
41
Conclusão
 A Internet cresce de forma rápida e não estruturada
 Necessidade de ferramentas de RI mais eficientes
 Aumento da demanda de armazenamento e
processamento de sistemas de RI
 Apesar dos avanços, é muito difícil resolver estes
problemas de forma definitiva
42