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