A universal online caching algorithm based on pattern matching

DOI10.1007/S00453-008-9196-9MaRDI QIDQ848635zbMATH OpenOpenAlexFDO

Authors Gopal Pandurangan, Wojciech Szpankowski

Publication date 4 March 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9196-9

zbMATH Keywords

CachingOnline computationStochastic modelUniversal algorithm

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Recommendations

• scientific article; zbMATH DE number 1305389
• scientific article; zbMATH DE number 1303544
• An \(O(\log k)\)-competitive algorithm for generalized caching
• On-line file caching
• The complexity of paging against a probabilistic adversary

Cites work

• scientific article; zbMATH DE number 3128728 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A universal algorithm for sequential data compression
• A universal predictor based on pattern matching
• Algorithms on Strings, Trees and Sequences
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Can entropy characterize performance of online algorithms?
• Competitive paging algorithms
• Compression of individual sequences via variable-rate coding
• Markov Paging
• On sequential strategies for loss functions with memory
• Optimal prefetching via data compression
• Paging against a distribution and IP networking
• Principles of Optimal Page Replacement
• Probability and Computing
• Some Distribution-Free Aspects of Paging Algorithm Performance
• Universal prediction
• Universal prediction of individual sequences
• Universal schemes for prediction, gambling and portfolio selection

Cited in

(1)

• Competitive Caching with Machine Learned Advice

This page was built for publication: A universal online caching algorithm based on pattern matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848635)