[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:5194 |
| Date | 16 July 2004 |
| 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.0017 seconds