Engenhos de Busca WebEquipe: Cássio Melo, Alexandre Barza, Manuela Nascimento e Rodrigo Freitas

{cam2, ab, mcn, rqf}

Jul/2007

RoteiroEvolução e Desafios;Arquitetura;Rankeamento;

Authorities, Hubs, Hits, PageRank e Hilltop;Spiders; Estratégias de Busca;Indexação;Browsing;Metabuscas;Conclusão.

Evolução WebGigantesco e ubíquo banco de dados, sem

estrutura definida.Como se comunicar ?

Evolução Web1990 - Tim Berners-Lee do CERN(Conseil

Européen pour la Recherche Nucleaire) cria o WWW;

Libwww, Erwise, Voilawww, Mosaic(NCSA), etc...

Evolução WebEm 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."- Brewster Kahle, fundador do The Internet Archive

DesafiosDados: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.

DesafiosPessoas:Especificar Consulta.Interpretar a resposta.

Objetivo:

Respostas relevantes para cada consulta.

ArquiteturasSistemas RI padrão + WEBPrincipais arquiteturas

Arquitetura centralizadaArquitetura distribuída

Arquitetura Centralizada

Query Engine

IndexIndexer

Web

Arquitetura CentralizadaArquitetura CentralizadaPrincipais problemas:

Sobrecarga dos servidoresAumento de tráfego (spiders)Informação recolhida sem coordenação

Arquitetura Distribuida

AuthoritiesDefiniçã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

AuthoritiesAuthorities for query: “Java”

java.sun.comcomp.lang.java FAQ

Authorities for query “search engine”Yahoo.comExcite.comLycos.comAltavista.com

Authorities for query “Gates”Microsoft.comroadahead.com

HubsDefiniçã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 HubsNa 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 boasautoridades.

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 subgrafoHubs apontam para muitas autoridades.Autoridades são apontadas por muitos hubs.

Hubs Authorities

PageRankAtribui 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.

PageRankMedida de importância de uma página para o Google.Download da barra de ferramentas do Google.

Page Rank

PageRankFalhas:

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 HilltopO 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 IPEx.: 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 HilltopO 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 sitesEntram 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

26

Busca em Largura

Estratégias de Busca

27

Busca em Profundidade

Prós e Contras…Busca em largura requer muita memória para

guardar todos os nós do nível anteriorporém é o método padrão utilizado.

Busca em profundidade necessita de menos memóriaporém pode se “perder” em um único nó, dada

a alta conectividade da Web.

28

Spider Multi-tarefaFazer o download de páginas é o

“Gargalo” dos engenhos de buscaMelhor ter múltiplas “threads” rodando

em hosts diferentesMaximizar 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 LinkMonitora links e verifica o in-degree e out-

degree de cada página encontrada.

31

Spidering direcionado ao LinkBusca 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áliseAnálise do FormatoReconhecimento de LinguagemProcessamento de Linguagem Natural

Eliminação de stopwordsOperações de normalização

Pontuação, espaços, uppercase,...TokenizationReconhecimento da SeçãoIndexação de Meta Tag

34

IndexaçãoA maioria dos sistemas web usam

variantes do arquivo invertidoLista 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 ÍndicesConsulta é respondida através de busca

binária no arquivo de índicesConsulta 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 ÍndicesArquivos de índices invertidos também

podem armazenar as ocorrências das palavras nos documentos (full inversion)Maior custo de armazenagemPossibilidade de consultas por frases e

expressões através da proximidade das palavras no documento

37

Busca no Arquivo de ÍndicesPara encontrar palavras que iniciam com

um dado prefixo, é necessário fazer duas buscas binárias na lista de palavras ordenadasEx.: 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

BrowsingDiretó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íficoMuitas ferramentas de busca são híbridas

Exemplo: Yahoo!

39

BrowsingDiretó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

MetabuscasServidores 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

VantagensHabilidade em unificar resultados de várias

origensUtilização de uma interface única

41

ConclusãoA Internet cresce de forma rápida e não

estruturadaNecessidade de ferramentas de RI mais

eficientesAumento da demanda de armazenamento e

processamento de sistemas de RIApesar dos avanços, é muito difícil resolver

estes problemas de forma definitiva

42