research-article

An O(log k)-Competitive Algorithm for Generalized Caching

Authors:

Anna Adamaszek,

Artur Czumaj,

Matthias Englert,

Harald RäckeAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 15, Issue 1

Article No.: 6, Pages 1 - 18

https://doi.org/10.1145/3280826

Published: 16 November 2018 Publication History

Get Access

Abstract

In the generalized caching problem, we have a set of pages and a cache of size k. Each page p has a size w_p≥ 1 and fetching cost c_p for loading the page into the cache. At any point in time, the sum of the sizes of the pages stored in the cache cannot exceed k. The input consists of a sequence of page requests. If a page is not present in the cache at the time it is requested, it has to be loaded into the cache, incurring a cost of c_p.

We give a randomized O(log k)-competitive online algorithm for the generalized caching problem, improving the previous bound of O(log² k) by Bansal, Buchbinder, and Naor (STOC’08). This improved bound is tight and of the same order as the known bounds for the classic paging problem with uniform weights and sizes. We use the same LP-based techniques as Bansal et al. but provide improved and slightly simplified methods for rounding fractional solutions online.

References

[1]

Dimitris Achlioptas, Marek Chrobak, and John Noga. 2000. Competitive analysis of randomized paging algorithms. Theoretical Computer Science 234, 1--2 (2000), 203--218.

Digital Library

Google Scholar

[2]

Susanne Albers, Sanjeev Arora, and Sanjeev Khanna. 1999. Page replacement for general caching problems. In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA). Baltimore, MD, Society for Industrial and Applied Mathematics, 31--40.

Digital Library

Google Scholar

[3]

Nikhil Bansal, Niv Buchbinder, and Joseph Naor. 2012. A primal-dual randomized algorithm for weighted paging. Journal of the ACM 59, 4 (2012), 19.

Digital Library

Google Scholar

[4]

Nikhil Bansal, Niv Buchbinder, and Joseph Naor. 2012. Randomized competitive algorithms for generalized caching. SIAM Journal of Computing 41, 2 (2012), 391--414.

Digital Library

Google Scholar

[5]

Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. 2001. A unified approach to approximating resource allocation and scheduling. Journal of the ACM 48, 5 (2001), 1069--1090.

Digital Library

Google Scholar

[6]

Niv Buchbinder and Joseph Naor. 2009. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research 34, 2 (2009), 270--286.

Digital Library

Google Scholar

[7]

Pei Cao and Sandy Irani. 1997. Cost-aware WWW proxy caching algorithms. In Proceedings of the USENIX Symposium on Internet Technologies and Systems. Monterey, CA, USENIX Assocation, 193--206.

Digital Library

Google Scholar

[8]

Marek Chrobak, Howard J. Karloff, T. H. Payne, and Sundar Vishwanathan. 1991. New results on server problems. SIAM Journal on Discrete Mathematics 4, 2 (1991), 172--181.

Digital Library

Google Scholar

[9]

Edith Cohen and Haim Kaplan. 2002. Caching documents with variable sizes and fetching costs: An LP-based approach. Algorithmica 32, 3 (2002), 459--466.

Digital Library

Google Scholar

[10]

Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, and Neal E. Young. 1991. Competitive paging algorithms. Journal of Algorithms 12, 4 (1991), 685--699.

Digital Library

Google Scholar

[11]

Sandy Irani. 2002. Page replacement with multi-size pages and applications to web caching. Algorithmica 33, 3 (2002), 384--409.

Crossref

Google Scholar

[12]

Lyle A. McGeoch and Daniel D. Sleator. 1991. A strongly competitive randomized paging algorithm. Algorithmica 6, 6 (1991), 816--825.

Digital Library

Google Scholar

[13]

Daniel D. Sleator and Robert E. Tarjan. 1985. Amortized efficiency of list update and paging rules. Communications of the ACM 28, 2 (1985), 202--208.

Digital Library

Google Scholar

[14]

Neal E. Young. 2002. On-line file caching. Algorithmica 33, 3 (2002), 371--383.

Crossref

Google Scholar

Cited By

View all

Dallot JFesharaki APacut MSchmid S(2024)Dependency-Aware Online CachingIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621422(871-880)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621422
Li GTan HZhang XZhang CZhou RHan ZChen G(2024)Online Container Caching with Late-Warm for IoT Data Processing2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00127(1547-1560)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00127
Zhang ZLuo ZWu C(2023)Two-level Graph Caching for Expediting Distributed GNN TrainingIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228911(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10228911
Show More Cited By

Index Terms

An O(log k)-Competitive Algorithm for Generalized Caching
1. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms
      1. Caching and paging algorithms

Recommendations

Competitive Algorithms for Block-Aware Caching
SPAA '22: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
Motivated by the design of real system storage hierarchies, we study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evicting) just one ...
Randomized competitive algorithms for generalized caching
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

We consider online algorithms for the generalized caching problem. Here we are given a cache of size k and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages ...
An O(log k)-competitive algorithm for generalized caching
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

In the generalized caching problem, we have a set of pages and a cache of size k. Each page p has a size w_p ≥ 1 and fetching cost c_p for loading the page into the cache. At any point in time, the sum of the sizes of the pages stored in the cache cannot ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 15, Issue 1

January 2019

366 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3281277

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 November 2018

Accepted: 01 September 2018

Revised: 01 January 2018

Received: 01 February 2016

Published in TALG Volume 15, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Engineering and Physical Sciences Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
292
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dallot JFesharaki APacut MSchmid S(2024)Dependency-Aware Online CachingIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621422(871-880)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621422
Li GTan HZhang XZhang CZhou RHan ZChen G(2024)Online Container Caching with Late-Warm for IoT Data Processing2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00127(1547-1560)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00127
Zhang ZLuo ZWu C(2023)Two-level Graph Caching for Expediting Distributed GNN TrainingIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228911(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10228911
Coester CLevin RNaor JTalmon OAgrawal KLee I(2022)Competitive Algorithms for Block-Aware CachingProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538567(161-172)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538567
Bansal NNaor JTalmon OAgrawal KAzar Y(2021)Efficient Online Weighted Multi-Level PagingProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461801(94-104)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461801

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Competitive Algorithms for Block-Aware Caching

Randomized competitive algorithms for generalized caching

An O(log k)-competitive algorithm for generalized caching