On-line file caching
From MaRDI portal
Publication:1601028
Abstract: 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.
Recommendations
Cited in
(41)- Object Caching for Queries and Updates
- On generalized connection caching
- Caching is hard -- even in the fault model
- On-line algorithm of loose competitive caching
- Online file caching with rejection penalties
- Economical caching
- scientific article; zbMATH DE number 1875407 (Why is no real title available?)
- Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis
- Resource Management in Large Networks
- A universal online caching algorithm based on pattern matching
- On Certain New Models for Paging with Locality of Reference
- Economical Caching with Stochastic Prices
- On-line restricted caching
- Tight bounds for double coverage against weak adversaries
- Online companion caching
- Calculating lower bounds for caching problems
- An analysis of optimum caching
- Online hierarchical cooperative caching
- Page replacement with multi-size pages and applications to web caching
- Online paging and file caching with expiration times
- Optimal prepaging and font caching
- scientific article; zbMATH DE number 1875410 (Why is no real title available?)
- Online Compression Caching
- scientific article; zbMATH DE number 4049014 (Why is no real title available?)
- An \(O(\log k)\)-competitive algorithm for generalized caching
- Stochastic dominance and the bijective ratio of online algorithms
- The relative worst-order ratio applied to paging
- Cost-Aware Caching Algorithms for Distributed Storage Servers
- Caching Content under Digital Rights Management
- On variants of file caching
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- More on weighted servers or FIFO is better than LRU.
- Parameterized analysis of paging and list update algorithms
- Approximating hit rate curves using streaming algorithms
- scientific article; zbMATH DE number 1542836 (Why is no real title available?)
- On the Relative Dominance of Paging Algorithms
- scientific article; zbMATH DE number 1617255 (Why is no real title available?)
- On the relative dominance of paging algorithms
- Economical caching
- scientific article; zbMATH DE number 1947417 (Why is no real title available?)
- On the separation and equivalence of paging strategies and other online algorithms
This page was built for publication: On-line file caching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1601028)
