Asymptotic optimality of the static frequency caching in the presence of correlated requests |
| |
Authors: | Predrag R Jelenkovi Ana Radovanovi |
| |
Institution: | aDepartment of Electrical Engineering, Columbia University, New York, NY 10027, United States;bGoogle, Inc., New York, NY 10011, United States |
| |
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. |
| |
Keywords: | Web caching Cache fault probability Average-case analysis Least-frequently-used caching Least-recently-used caching Long-range dependence |
本文献已被 ScienceDirect 等数据库收录! |
|