Asymptotic optimality of the static frequency caching in the presence of correlated requests

Asymptotic optimality of the static frequency caching in the presence of correlated requests

0.00 Avg rating0 Votes
Article ID: iaor20102982
Volume: 37
Issue: 5
Start Page Number: 307
End Page Number: 311
Publication Date: Sep 2009
Journal: Operations Research Letters
Authors: ,
Keywords: computational analysis
Abstract:

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 identically 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.

Reviews

Required fields are marked *. Your email address will not be published.