Page replacement for general caching problems

Susanne Albers, Sanjeer Arora, Sanjeer Khanna

Research output: Contribution to conferencePaperpeer-review

81 Scopus citations

Abstract

Caching (paging) is a well-studied problem in online algorithms, usually studied under the assumption that all pages have a uniform size and a uniform fault cost (uniform caching). However, recent applications related to the web involve situations in which pages can be of different sizes and costs. This general caching problem seems more intricate than the uniform version. In particular, the offline case itself is NP-hard. Only a few results exist for the general caching problem. This paper seeks to develop good of online page replacement policies for the general caching problem, with the hope that any insight gained here may lead to good online algorithms. Our first main result is that by using only a small amount of additional memory, say O(1) times the largest page size, we can obtain an O(1)-approximation to the general caching problem. Note that the largest page size is typically a very small fraction of the total cache size, say 1%. Our second result is that when no additional memory is allowed, one can obtain an O(log(M+C))-approximation where and C denote the cache size and the largest page fault cost, respectively. Our results use a new rounding technique for linear programs which may be of independent interest. We also present a randomized online algorithm for the Bit Model which achieves a competitive ratio of O(ln(1+1/c)) while using M(1+c) memory.

Original languageEnglish (US)
Pages31-40
Number of pages10
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Page replacement for general caching problems'. Together they form a unique fingerprint.

Cite this