Asymptotic Optimality of the Static Frequency Caching in the Presence of Correlated Requests

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

It is well known that the static caching algorithm that keeps the most frequently requested documents in the cache is optimal in case when documents are of the same size and requests are independent and equally distributed. However, it is hard to develop explicit and provably optimal caching algorithms when requests are statistically correlated. In this paper, we show that keeping the most frequently requested documents in the cache is still optimal for large cache sizes even if the requests are strongly correlated.

Keywords

Performance, Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/224983

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0903.4898
 http://arxiv.org/abs/0903.4898

Collections

arXiv