[pt] ALGORITMOS EFICIENTES PARA ATRIBUIÇÃO DE HOTLINKS EM DIRETÓRIOS WEB

• Ano de defesa: 2004
• Autor(a) principal: CRISTON PEREIRA DE SOUZA
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] PROGRAMACAO INTEIRA; [pt] ALGORITMOS APROXIMADOS; [pt] PROGRAMACAO DINAMICA; [pt] INTERNET; [en] INTER LINEAR PROGRAMMIN; [en] APPROXIMATION ALGORITHMS; [en] DYNAMIC PROGRAMMING; [en] INTERNET
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5194&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5194&idi=2; http://doi.org/10.17771/PUCRio.acad.5194

[pt] Uma maneira de localizar uma informação em uma base de dados grande e caótica como a Internet é utilizar um índice hierárquico que respeita alguma maneira de categorizar os dados. Exemplos desta hierarquia são os serviços de diretório, comuns em sites de busca. Porém, esta abordagem pode apresentar algumas desvantagens, como a necessidade de percorrer muitas páginas até chegar em uma informação muito acessada. Uma maneira de tratar este problema é o uso de hotlinks, hyperlinks adicionais que servem como atalho em uma busca. Estudamos algoritmos eficientes para atribuir hotlinks em um diretório web, de modo a reduzir o número máximo ou o número médio de acessos em uma busca. Fornecemos para o problema de minimização do número máximo de acessos um algoritmo (14/3)-aproximado e um algoritmo polinomial exato baseado em programação dinâmica. Por outro lado, para o problema de minimizar o número médio de acessos, adaptamos o algoritmo exato do problema anterior. Entretanto, este algoritmo adaptado é polinomial apenas para sites representados por árvores com altura O(log n). Por isso, introduzimos um parâmetro que permite ao usuário reduzir o tempo de execução em detrimento da qualidade da solução. Para este problema de minimizar o número médio de acessos, realizamos também experimentos comparando nosso algoritmo, um modelo em programação inteira, e alguns algoritmos propostos por outros autores. Introduzimos modificações práticas que melhoraram a performance do nosso algoritmo.