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

CRISTON PEREIRA DE SOUZA

[en] EFFICIENT HOTLINKS ASSIGMENT ALGORITHM FOR WEB DIRECTORIES

dc.contributor	EDUARDO SANY LABER
dc.creator	CRISTON PEREIRA DE SOUZA
dc.date	2004-07-16
dc.date.accessioned	2022-09-21T21:43:57Z
dc.date.available	2022-09-21T21:43:57Z
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5194@1
dc.identifier	https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5194@2
dc.identifier	http://doi.org/10.17771/PUCRio.acad.5194
dc.identifier.uri	https://hdl.handle.net/20.500.12032/42778
dc.description	[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.
dc.description	[en] An approach to search an information in a large and chaotic data base like the Internet is to use a hierarquical index regarding some categorization of the data. As an example, we have the web directories, usually found in search engines. However, this approach may have problems, as the need of visiting too many web pages to find a very accessed information. A way to address this problem is the use of hotlinks, which are hyperlinks added to the web site and used as shortcuts in a search. We studied efficient algorithms to assign hotlinks in web directories, in such a way to minimize the maximum or the average number of accesses to find an information. For the problem of minimizing the maximum number of accesses, we provide an (14/3)-approximation algorithm and an exact polinomial time algorithm based on dynamic programming. On the other hand, for the problem of minimizing the expected number of accesses, we adapted the previous exact algorithm. However, this adapted algorithm is polinomial only for web sites represented by trees with height O(log n). So, we introduce a parameter that allows the user to reduce the execution time under the cost of reducing the solution quality. For this problem of minimizing the expected number of accesses, we also made experiments comparing our algorithm, an integer programming model, and some algorithms proposed by other authors. We introduce pratical changes that improved the performance of our algorithm.
dc.language	pt
dc.publisher	MAXWELL
dc.subject	[pt] PROGRAMACAO INTEIRA
dc.subject	[pt] ALGORITMOS APROXIMADOS
dc.subject	[pt] PROGRAMACAO DINAMICA
dc.subject	[pt] INTERNET
dc.subject	[en] INTER LINEAR PROGRAMMIN
dc.subject	[en] APPROXIMATION ALGORITHMS
dc.subject	[en] DYNAMIC PROGRAMMING
dc.subject	[en] INTERNET
dc.title	[pt] ALGORITMOS EFICIENTES PARA ATRIBUIÇÃO DE HOTLINKS EM DIRETÓRIOS WEB
dc.title	[en] EFFICIENT HOTLINKS ASSIGMENT ALGORITHM FOR WEB DIRECTORIES
dc.type	TEXTO

Files in this item

Files	Size	Format	View
There are no files associated with this item.

This item appears in the following Collection(s)

Documentos - PUC-RIO

Show simple item record