Universidade Técnica de Lisboa
Instituto Superior Técnico
Recuperação de Informação
The Anatomy of a Large-Scale
Hypertextual Web Search Engine
Sergey Brin and Lawrence Page
Adriano Kaminski Sanches
Prof. Dr. Pável Calado
Novembro de 2007
Contéudo
Introdução
Características do Sistema
Trabalhos Relacionados
Anatomia do Sistema
Resultados e Desempenho
Conclusão
Contexto
1998
Conteúdo da Internet Crescendo
2 Soluções existentes:
Índices mantidos por humanos
Buscadores automáticos
Necessidade de Soluções de Busca
Introdução
Resultado?
= googol = 10100
Introdução
Protótipo de um motor de busca de larga
escala
Objectivo principal:
Aumentar a qualidade dos resultados em busca
na internet
Em Novembro de 2007, somente 1 dos 4 maiores motores de
busca conseguiam se achar
Objectivo secundário:
Acompanhar o rápido crescimento da internet,
sendo escalável
Introdução
1993 --» 1.5% .com
1997 --» 60% .com
Motores de busca: universidade »» empresas
Empresas guardavam segredos dos buscadores
Ausência de material científico sobre o tema
Google --» preencher essa lacuna
Características do Sistema
Duas importantes características:
PageRank
Trazendo Ordem para a Web
Uso dos Links (ãncoras)
Características do Sistema
PageRank
A importância de uma página --» popularidade
Colectou-se todos os links da coleção (origem e
destino)
Criou-se um mapa de links --»518 milhões de
hyperlinks
Para cada página
De onde vem
Para onde vai
Características do Sistema
Cálculo do PageRank:
“Vamos assumir que a Página A tenha as páginas
T1..Tn que apontam para ela
Parametro D é um damping factor (entre 0 e 1)
C(A) é o número de links que saem de A
PR(A) = (1-d) + d(PR(T1)/C(T1)+…+PR(Tn)/C(Tn)”
Características do Sistema
Cálculo do PageRank:
Se uma Página A é muito citada --» PR(A)
↑
Se uma Página A é citada por páginas populares
--» PR(A)
↑
Características do Sistema
Ãncoras de Texto:
Levar em consideração textos das ãncoras
casos que ãncoras dizem mais que a própria página
ãncoras são valiosas para documentos que não podem
ser indexados: imagens, programas, banco de dados…
Na coleção de 24 milhões de páginas -» 259 milhões
de ãncoras indexadas
Características do Sistema
Outras características:
Armazena localização de cada palavra no texto
Armazena detalhes visuais (tamanho da fonte,
estilo)
Toda a coleção rastreada da internet é
armazenada em repositórios próprios
Trabalhos Relacionados
Trabalhos de pesquisa na Web?
Poucos
Internet Cresceu -» Pesquisa aberta diminuiu
Pesquisa comercial apenas
Trabalhos de pesquisa em colecções controladas?
Muita pesquisa em Recuperação de Informação
Serve para a web?
web != colecções controladas
O “Very Large Corpus” do TREC de 1996 tinha um benchmark de 20
GB, google tinha 147 GB
O usuário não precisa refinar a busca
Anatomia do Sistema
Anatomia do Sistema
Repositório
Lista sequencial de todas páginas comprimidas
Compressão utilizada, meio termo entre velocidade e taxa de
compressão
zlib 3 para 1
é armazenado o docID, tamanho, e URL também (além do
documento comprimido)
é o suficiente para reconstruir as páginas armazenadas.
Índice de documentos
Mantém informações sobre cada página
Índice sequencial
Estado do documento, ponteiro para o repositório, checksum do
documento e varias estatísticas
Anatomia do Sistema
Lexicon
Dicionário de 14 milhões de palavras
Tamanho reduzido 293 MB
Lista de Hit
Lista com a ocorrência de uma palavra particular, incluindo posição,
tamanho da fonte e informação se maiúscula ou minúscula
Ocupa grande parte dos dados
Informações úteis para calcular PageRank
Anatomia do Sistema
Forward Index
Lista com todos os Hits de cada palavra de cada documento
Índice invertido
Forward Index ordenada por palavras
Cada palavra no Lexicon tem um ponteiro para a lista de ocorrências
desta palavra em cada documento neste índice
Dois índices:
1 com as ocorrências de palavras apenas nas ãncoras e títulos de
páginas
outro completo com todas as ocorrências
Anatomia do Sistema
Buscando Páginas na WEB
Parte mais sensível, pois depende de factores externos
Apenas 1 URLserver alimenta os vários robôs de busca
Tipicamente utilizado 3 robôs
Implementado em Python
Cada robô mantém 300 conexões ao mesmo tempo
Chega a buscar 100 páginas web por segundo
Problemas com mails/telefonemas
Anatomia do Sistema
Indexando a WEB
Separação das palavras (Parse dos Tokens)
Flex
Indexando documentos nos Barrels
Cada Palavra é convertida em uma wordID que será utilizada no Lexicon
Cada ocorrência da wordID no documento corrente é traduzida para um
hit list e escrito no índice.
Problemas com paralelização: Lexicon Estático, lista extra com palavras
novas
Indexando a lista invertida
Transforma a lista indexada, que esta ordenada por ocorrência de
palavras dentro de cada documento, em uma lista sequencial com as
ocorrências de cada palavra em todos os documentos
Anatomia do Sistema
Buscas por palavra-chave
Objectivo principal:
aumentar a qualidade dos resultados
Entretanto, sistema com capacidade de crescer
1.
2.
3.
4.
5.
6.
7.
8.
Separe a query
Converta as palavras em wordIDs
Vá para o início da lista de índice invertido pequeno de cada palavra
da query
Percorra a lista até achar um documento que case todos os termos
Compute o rank desse documento
Se está no final da lista pequena e teve poucos resultados, percorra
a lista grande e vá para o passo 4
Se não está no final de qualquer lista, vá para o passo 4
Ordene os elementos que casaram os termos e mostre por ordem
de importância
Resultados e Desempenho
Qualidade das respostas -» subjetivos
Superou barreiras que concorrentes não atingiam
Números mais apurados necessitam de um teste extensivo
e independente
Storage Statistics
Web Page Statistics
Number of Web
Pages Fetched
24
million
Number of Urls
Seen
76.5
million
Number of Email
Addresses
1.7
million
Number of 404's
1.6
million
Total Size of Fetched
Pages
147.8
GB
Compressed Repository
53.5 GB
Short Inverted Index
4.1 GB
Full Inverted Index
37.2 GB
Lexicon
293 MB
Temporary Anchor Data
(not in total)
6.6 GB
Document Index Incl.
Variable Width Data
9.7 GB
Links Database
3.9 GB
Total Without
Repository
55.2
GB
Total With Repository
108.7
GB
Initial Query
Same Query
Repeated (IO
mostly cached)
Quer
y
CPU
Tim
e(s)
Total
Time
(s)
CPU
Time(s)
Total
Time(s)
al
gore
0.09
2.13
0.06
0.06
vice
presi
dent
1.77
3.84
1.66
1.80
hard
disks
0.25
4.86
0.20
0.24
searc
h
engin
es
1.31
9.63
1.16
1.16
Conclusão
Google é um sistema completo de busca
Primeiro objectivo alcançado (melhorar a qualidade das
respostas a uma query)
Para chegar neste resultado -» novas técnicas
PageRank, ãncoras, proximidade
Com algumas simples mudanças Google suporta maior
número de dados (escalável)
Conclusão
Trabalhos Futuros
Muito tem a ser feito
Melhorar a eficiência das buscas para 100 milhões de páginas
Cache de query
subindices
updates
proxy caches
Adicionar buscas com operadores booleanos
Contexto do usuário
…
http://www.google.com/options/index.html
Muito Obrigado!
Universidade Técnica de Lisboa
Instituto Superior Técnico
Recuperação de Informação
The Anatomy of a Large-Scale
Hypertextual Web Search Engine
Sergey Brin and Lawrence Page
Adriano Kaminski Sanches
Prof. Dr. Pável Calado
Novembro de 2007