On-Line File Caching

Details On-Line File Caching On-Line File Caching

2002-05-18

arxiv.org/abs/cs/0205033v1

Algorithmica 33:371-383 (2002)

Computer Science

Data Structures and Algorithms

ACM-SIAM Symposium on Discrete Algorithms (1998)

Scientific paper

In the on-line file-caching problem problem, the input is a sequence of requests for files, given on-line (one at a time). Each file has a non-negative size and a non-negative retrieval cost. The problem is to decide which files to keep in a fixed-size cache so as to minimize the sum of the retrieval costs for files that are not in the cache when requested. The problem arises in web caching by browsers and by proxies. This paper describes a natural generalization of LRU called Landlord and gives an analysis showing that it has an optimal performance guarantee (among deterministic on-line algorithms). The paper also gives an analysis of the algorithm in a so-called ``loosely'' competitive model, showing that on a ``typical'' cache size, either the performance guarantee is O(1) or the total retrieval cost is insignificant.

Affiliated with

Also associated with

No associations

Rating

On-Line File Caching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On-Line File Caching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-Line File Caching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599126