gra2003-01

Adaptive caching by experts

by:
Robert B. Gramacy

ABSTRACT

We are constructing caching policies that have 15-22% lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 45--70% 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 develop a master policy, which dynamically combines the recommendations of a pool of standard policies based on their observed success. The framework outlined in this paper is a paradigm shift for the design of caching strategies. Our approach is attractive because it is simple, adaptive, scalable, and gives impressive results. 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

@TECHREPORT{gra2003:thesis,       Author = {Robert B. Gramacy},       Institution = {University of Californina, Santa Cruz},       Title = {Adaptive Caching by experts, {M}asters {T}hesis},       Year = {2003},       Url = {http://www.ams.ucsc.edu/~rbgramacy/papers/gra2003-01.pdf}       }

click to download .pdf