Learning to schedule web page updates using genetic programming
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Edleno Silva de Moura
Wagner Meira Junior
Ana Carolina Brandao Salgado
Wagner Meira Junior
Ana Carolina Brandao Salgado
Resumo
Um dos principais desafios enfrentados durante o desenvolvimento de políticas de escalonamento para atualizações de páginas web é estimar a probabilidade de uma página que já foi coletada previamente ser modificada na Web. Esta informação pode ser usada pelo escalonador de um coletor de páginas web para determinar a ordem na qual as páginas devem ser recoletadas, permitindo ao sistema reduzir o custo total de monitoramento das páginas coletadas para mantê-las atualizadas. Nesta dissertação é apresentada uma nova abordagem que usa aprendizado de máquina para gerar funções de score que produzem listas ordenadas de páginas com relação a probabilidade deterem sido modificadas na Web quando comparado com a última versão coletada. É proposto um arcabouço flexível que usa Programação Genética para evoluir funções que estimam a probabilidade de a página ter sido modificada. É apresentado ainda uma avaliação experimental dos benefícios de usar o arcabouço proposto em relação a cinco abordagens estado-da-arte. Considerando a métrica Change Ratio, os valores produzidos pela melhor função gerada pelo arcabouço proposto mostram uma melhora de 0.52 para 0.71, em média, em relação aos baselines.
Abstract
One of the main challenges endured when designing a scheduling policy regarding freshness is to estimate the likelihood of a previously crawled web page being modified on the web, so that the scheduler can use this estimation to determine the order in which those pages should be visited. A good estimation of which pages have more chance of being modified allows the system to reduce the overall cost of monitoring its crawled web pages for keeping updated versions. In this work we present a novel approach that uses machine learning to generate score functions that produce accurate rankings of pages regarding their probability of being modified on the Web when compared to their previously crawled versions. We propose a flexible framework that uses Genetic Programming to evolve score functions to estimate the likelihood that a web page has been modified. We present a thorough experimental evaluation of the benefits of using the framework over five state-of-the-art baselines. Considering the Change Ratio metric, the values produced by our best evolved function show an improvement from 0.52 to 0.71 on average over the baselines.
Assunto
Programação genética (Computação), Computação, Sistemas de recuperação da informação
Palavras-chave
Coleta incremental de páginas web, Programação genética, Políticas de escalonamento