Adaptive caching by refetching

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