A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Design Framework for Online Algorithms Solving the Object Replacement Problem Uma estrutura de design para algoritmos online que resolve o problema de substituição de objetos

Seiichiro TANI, Toshiaki MIYAZAKI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Os caches de rede reduzem o tráfego de rede e também o tempo de resposta do usuário. Ao implementar caches de rede, o problema de substituição de objetos é um dos principais problemas; O problema é determinar quais objetos devem ser removidos de um cache quando não houver espaço suficiente. Este artigo primeiro formaliza o problema e fornece uma condição simples, mas suficiente para que algoritmos determinísticos online sejam competitivos. Com base na condição, é construída uma estrutura geral para tornar competitivo um algoritmo não competitivo. Como aplicação do framework, é proposto um algoritmo online, denominado Competitive_SIZE. Ambas as simulações orientadas por eventos e por rastreamento mostram que Competitive_SIZE é melhor do que algoritmos propostos anteriormente, como LRU (Least Recentemente Usado).

Publicação
IEICE TRANSACTIONS on Information Vol.E84-D No.9 pp.1135-1143
Data de publicação
2001/09/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Algoritmos

autores

Palavra-chave