On-line file caching

DOI10.1007/S00453-001-0124-5zbMATH Open0994.68182arXivcs/0205033OpenAlexW3125910951MaRDI QIDQ1601028FDOQ1601028

Authors: Neal E. Young 

Publication date: 17 June 2002

Published in: Algorithmica (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0205033

Recommendations

• scientific article; zbMATH DE number 1303544
• Online paging and file caching with expiration times
• On-line algorithm of loose competitive caching
• scientific article; zbMATH DE number 1305389
• On variants of file caching

zbMATH Keywords

caching problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cited In (41)

• 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
• Title not available (Why is that?)
• Economical caching
• Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis
• Resource Management in Large Networks
• On Certain New Models for Paging with Locality of Reference
• A universal online caching algorithm based on pattern matching
• 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
• Page replacement with multi-size pages and applications to web caching
• Online hierarchical cooperative caching
• Online paging and file caching with expiration times
• Optimal prepaging and font caching
• Title not available (Why is that?)
• An \(O(\log k)\)-competitive algorithm for generalized caching
• Online Compression Caching
• Title not available (Why is that?)
• 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
• Parameterized analysis of paging and list update algorithms
• More on weighted servers or FIFO is better than LRU.
• Approximating hit rate curves using streaming algorithms
• Title not available (Why is that?)
• On the Relative Dominance of Paging Algorithms
• Title not available (Why is that?)
• Economical caching
• On the relative dominance of paging algorithms
• Title not available (Why is that?)
• On the separation and equivalence of paging strategies and other online algorithms
• Object Caching for Queries and Updates

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)