[en] EFFICIENT WEB PAGE REFRESH POLICIES - CRISTON PEREIRA DE SOUZA (2010)
[pt] Uma máquina de busca precisa constantemente revisitar páginas Web para manter seu repositório local atualizado. Uma política de revisitação deve ser empregada para construir um escalonamento de revisitações que mantenha o repositório o mais atualizado possível utilizando os recursos disponíveis. Para evitar sobrecarga de servidores Web, a política de revisitação deve respeitar um tempo mínimo entre requisições consecutivas a um mesmo servidor. Esta regra é chamada restrição de politeness. Devido ao porte do problema, consideramos que uma política de revisitação é eficiente se o tempo médio para escalonar uma revisitação é sublinear no número de páginas do repositório. Neste sentido, quando a restrição de politeness é considerada, não conhecemos política eficiente com garantia teórica de qualidade. Nesta pesquisa investigamos três políticas eficientes que respeitam a restrição de politeness, chamadas MERGE, RANDOM e DELAYED. Fornecemos fatores de aproximação para o nível de atualização do repositório quando empregamos as política MERGE ou RANDOM. Demonstramos que 0,77 é um limite inferior para este fator de aproximação quando empregamos a política RANDOM, e apresentamos uma conjectura de que 0,927 é um limite inferior para este fator de aproximação quando empregamos a política MERGE. As políticas também são avaliadas através da simulação da execução destas políticas para manter o nível de atualização de um repositório contendo 14,5 milhões de páginas Web. Um repositório contendo artigos da Wikipedia também é utilizado nos experimentos, onde podemos observar que a política MERGE apresenta melhores resultados que uma estratégia gulosa natural para este repositório. A principal conclusão desta pesquisa é que existem políticas simples e eficientes para o problema de revisitação de páginas Web, que perdem pouco em termos do nível de atualização do repositório mesmo quando consideramos a restrição de politeness.