o problema
Em 1994, o World Wide Web Worm indexava 110.000 páginas e recebia cerca de 1.500 consultas por dia. Em novembro de 1997, o Altavista dizia responder 20 milhões de consultas diárias e os maiores buscadores alegavam índices de 2 a 100 milhões de documentos. A escala mudou de ordem de grandeza; a capacidade do usuário de olhar resultados, não. Ele continuava lendo as primeiras dezenas.
O resultado foi que completude deixou de ser o gargalo e qualidade virou o gargalo. Casamento de palavra-chave devolvia lixo demais: o paper conta que, em novembro de 1997, só um dos quatro maiores buscadores comerciais se encontrava ao ser buscado pelo próprio nome. O ferramental de recuperação de informação da época tinha sido calibrado em coleções pequenas e bem comportadas — o benchmark “Very Large Corpus” do TREC tinha 20 GB, contra os 147,8 GB do crawl de 24 milhões de páginas dos autores. O modelo de espaço vetorial, aplicado à web, premiava documentos curtíssimos: Brin e Page relatam um buscador grande devolvendo, para “Bill Clinton”, uma página com os dizeres “Bill Clinton Sucks” e uma foto. Pior: em 1993, 1,5% dos servidores web estavam em .com; em 1997, mais de 60%. Havia empresas cujo negócio era manipular buscadores, e qualquer texto na página que não fosse mostrado ao usuário — metadados, sobretudo — era abusado.
a ideia
Parar de julgar a página pelo que ela diz de si e passar a julgá-la pelo que a web diz dela. O grafo de links é uma rede de citações, e citação acadêmica já era um sinal conhecido de importância. A contribuição é não contar citação por cabeça: um link vale conforme a importância de quem o emite, dividida pelo número de links que essa página emite. Isso é recursivo, e a recursão é o ponto.
A justificativa que os autores dão é o “random surfer”: alguém que clica links ao acaso, nunca volta e, de vez em quando, se entedia e recomeça numa página aleatória. O PageRank de uma página é a probabilidade de esse navegante estar nela. O segundo movimento é mais barato e quase tão importante: o texto do link descreve melhor o destino do que o destino descreve a si mesmo, e serve para indexar coisas que nem são texto — imagens, programas, endereços de email.
como funciona
O PageRank de A, com páginas T1..Tn apontando para ela e C(X) sendo o número de links que saem de X:
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))O fator de amortecimento d fica em 0,85 e é a probabilidade de o navegante se entediar. Os PageRanks somam 1 sobre todas as páginas; o cálculo é iterativo.
O resto é engenharia de disco. Um URLserver distribui listas de URLs para os crawlers — três deles, escritos em Python, cerca de 300 conexões abertas cada, IO assíncrono, cache de DNS próprio, mais de 100 páginas por segundo no pico. O storeserver comprime as páginas com zlib (3 para 1; bzip dava 4 para 1 e foi descartado por velocidade) num repositório de onde tudo o mais pode ser reconstruído.
O indexer transforma cada documento em hits. Um hit ocupa dois bytes e carrega posição na página, tamanho de fonte relativo e capitalização; hits em título, URL, âncora ou meta tag são “fancy” e usam a fonte 7 como flag. Os hits vão para 64 barrels, formando um índice direto parcialmente ordenado; o sorter reordena cada barrel por wordID para produzir o índice invertido, um barrel por vez, sem precisar de espaço temporário grande. Existem dois conjuntos de barrels invertidos: um curto, só com hits de título e âncora, e o completo — a busca varre o curto primeiro e só desce para o grande se faltar resultado.
O URLresolver lê o arquivo de âncoras, resolve URLs relativas, joga o texto da âncora no índice direto do docID apontado e gera a base de links que alimenta o PageRank. Converter URL em docID é feito em lote, por merge com um arquivo de checksums ordenado: um seek por link, nos 322 milhões de links do dataset, levaria mais de um mês.
No ranking, cada tipo de hit tem um type-weight; as contagens viram count-weights que crescem e saturam; o produto escalar dos dois dá um score de IR, combinado depois com o PageRank. Em consulta de várias palavras, entra proximidade, classificada em dez faixas que vão de frase exata a “nem perto”.
o que isso custou
Devolver páginas nunca baixadas, com base só na âncora, significa devolver páginas que podem não existir — os autores admitem que o sistema pode retornar um endereço que nunca existiu, só porque havia links para ele. Não há validação antes de mostrar.
A latência é ruim: de 1 a 10 segundos por consulta, dominadas por IO sobre NFS, sem cache de consulta e sem subíndices para termos comuns. E há um corte grosseiro: achados 40.000 documentos que casam, o buscador para e ordena o que tem, aceitando resultado subótimo.
Os pesos do ranking são, nas palavras deles, uma arte negra, ajustada por feedback de usuários de confiança. A avaliação de qualidade é subjetiva e declarada como tal — não houve estudo com usuários. A codificação compacta cobra o seu: posição de palavra tem 12 bits, tudo além de 4095 é marcado como 4096, e hits de âncora ficam com 4 bits de posição mais 4 bits de hash do docID, o que só permite busca de frase limitada.
Sobre escala, a meta declarada é 100 milhões de páginas, e mesmo aí os autores esperam esbarrar em limites do sistema operacional: memória endereçável, descritores de arquivo, sockets. Passar muito disso, escrevem, aumentaria bastante a complexidade do sistema. Manipulação também fica em aberto: eles diagnosticam o problema, mencionam que amortecimento personalizado dificultaria a fraude, e param aí.
onde isso aparece hoje
A aposta central do apêndice B — indexação centralizada, apoiada em Moore, sai mais barata que qualquer arranjo distribuído entre voluntários — é a aposta que definiu a década seguinte de infraestrutura. Os 108,7 GB de 1998 viraram um problema de datacenter, e a linhagem está publicada: Web Search for a Planet: The Google Cluster Architecture descreve a máquina que serve essas consultas, The Google File System e MapReduce descrevem como se constrói um índice desse tamanho sem escrever sorters à mão, e Bigtable descreve onde o repositório de páginas acabou morando.
Rodar o cálculo de PageRank sobre o grafo inteiro virou um problema de sistemas por si só, endereçado depois por Pregel. Os aborrecimentos do crawler descritos aqui — variação infinita de páginas, lixo, duplicata — geraram trabalho próprio, como Detecting Near-Duplicates for Web Crawling. Do lado da relevância pura, a linha de recuperação de informação que este paper acusa de não funcionar na web seguiu evoluindo em paralelo, em BM25, e a ideia de pontuar documento por sinal externo ao texto sobreviveu inteira na recuperação densa e no ranking moderno.
Fica também o apêndice A, escrito por dois doutorandos que argumentavam que publicidade envenena a busca. O buscador que eles descrevem se financiou com publicidade.