gra2003-02

Adaptive caching by refetching

by:
Robert B. Gramacy, Manfred K. Warmuth, Scott A. Brandt, Ismail Ari

ABSTRACT

We are constructing caching policies that have 13-20% lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63% over Least Recently Used, the most commonly implemented policy. We achieve this not by designing a specific new policy but by using on-line Machine Learning algorithms to dynamically shift between the standard policies based on their observed miss rates. A thorough experimental evaluation of our techniques is given, as well as a discussion of what makes caching an interesting on-line learning problem.

BIBTEX

@inproceedings{gramacy03adaptive,       author = {R. B. Gramacy and M. K. Warmuth and S. A. Brandt and I. Ari},       title = {Adaptive Caching by Refetching},       booktitle = {Advances in Neural Information Processing Systems},       editor = {S. Becker, S. Thrun and K. Obermayer},       year = 2003,       publisher = {MIT Press},       address= {Cambridge, MA},       pages = {1465--1472},       url = {http://www.ams.ucsc.edu/~rbgramacy/papers/gra2003-02.pdf}      }

click to download .pdf