|
Abstract : |
We consider the paging problem where the pages have varying size. This problem has applications to page replacement policies for caches containing World Wide Web documents. We consider two models for the cost of an algorithm on a request sequence. In the rst, (the Fault model) the goal is to minimize the number of page faults. In the second, (the Bit model) the goal is to minimize the total numberofbitsthathave tobereadinto the cache. We show o ine algorithms for both cost models that obtain approximation factors of O(log k), where k is the ratio of the size of the cache to the size of the smallest page. We show randomized online algorithms for both cost models that are O(log 2 k)-competitive. In addition, if the input sequence is generated by aknown distribution, we show an algorithm for the Fault model whose expected cost is within a factor of O(log k) ofany other online algorithm. 1, |
