|
TITLE: Adaptive Caching by
Refetching
SPEAKER:
Manfred K. Warmuth
UC Santa Cruz
DATE: 2:00 - 3:00 P.M., Tuesday August 12, 2003
LOCATION: Half Dome, 3L (PA)
HOST: Vinay Deolalikar
ABSTRACT:
We are constructing caching strategies that consistently have
15-22% lower missrates 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 common
implemented baseline 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 the
pool of baseline policies by taking their observed recent
hitrates into account. Our methodology is a paradigm shift for
the design of caching strategies. Our approach is attractive
because it is simple, adaptive and scalable and gives impressive
results.
We give a thorough experimental evaluation of our techniques and
discuss what makes caching a challenging on-line learning
problem.
Joint work with Robert B. Gramacy and Scott Brandt
|
printable version
