[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. / [en] A search engine needs to continuously revisit web pages in order to
keep its local repository up-to-date. A page revisiting schedule must be
defined to keep the repository up-to-date using the available resources.
In order to avoid web server overload, the revisiting policy must respect
a minimum amount of time between consecutive requests to the same
server. This rule is called politeness constraint. Due to the large number
of web pages, we consider that a revisiting policy is efficient when the
mean time to schedule a revisit is sublinear on the number of pages in the
repository. Therefore, when the politeness constraint is considered, there
are no existing efficient policies with theoretical quality guarantees. We
investigate three efficient policies that respect the politeness constraint,
called MERGE, RANDOM and DELAYED. We provide approximation
factors for the repository’s up-to-date level for the MERGE and RANDOM
policies. Based on these approximation factors, we devise a 0.77 lower bound
for the approximation factor provided by the RANDOM policy and we
present a conjecture that 0.927 is a lower bound for the approximation
factor provided by the MERGE policy. We evaluate these policies through
simulation experiments which try to keep a repository with 14.5 million
web pages up-to-date. Additional experiments based on a repository with
Wikipedia’s articles concluded that the MERGE policy provides better
results than a natural greedy strategy. The main conclusion of this research
is that there are simple and efficient policies that can be applied to this
problem, even when the politeness constraint must be respected, resulting
in a small loss of repository’s up-to-date level.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:15893 |
| Date | 15 July 2010 |
| Creators | CRISTON PEREIRA DE SOUZA |
| Contributors | EDUARDO SANY LABER |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0014 seconds