nips nips2002 nips2002-20 nips2002-20-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: 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.
[AAG ar] Ismail Ari, Ahmed Amer, Robert Gramacy, Ethan Miller, Scott Brandt, and Darrell D. E. Long. ACME: Adaptive caching using multiple experts. In Proceedings of the 2002 Workshop on Distributed Data and Structures (WDAS 2002). Carleton Scientific, (to appear). ¤ [ACD 99] Martin Arlitt, Ludmilla Cherkasova, John Dilley, Rich Friedrich, and Tai Jin. Evaluating content management techniques for Web proxy caches. In Proceedings of the Workshop on Internet Server Performance (WISP99), May 1999. [BW02] O. Bousquet and M. K. Warmuth. Tracking a small set of experts by mixing past posteriors. J. of Machine Learning Research, 3(Nov):363–396, 2002. Special issue for COLT01. [CBFH 97] N. Cesa-Bianchi, Y. Freund, D. Haussler, D. P. Helmbold, R. E. Schapire, and M. K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427– 485, 1997. ¤ ¤ [CI97] Pei Cao and Sandy Irani. Cost-aware WWW proxy caching algorithms. In Proceedings of the 1997 Usenix Symposium on Internet Technologies and Systems (USITS-97), 1997. [HLSS00] David P. Helmbold, Darrell D. E. Long, Tracey L. Sconyers, and Bruce Sherrod. Adaptive disk spin-down for mobile computers. ACM/Baltzer Mobile Networks and Applications (MONET), pages 285–297, 2000. [HW98] M. Herbster and M. K. Warmuth. Tracking the best expert. Journal of Machine Learning, 32(2):151–178, August 1998. Special issue on concept drift. [JB00] Shudong Jin and Azer Bestavros. Greedydual* web caching algorithm: Exploiting the two sources of temporal locality in web request streams. Technical Report 2000-011, 4, 2000. [KW97] J. Kivinen and M. K. Warmuth. Additive versus exponentiated gradient updates for linear prediction. Information and Computation, 132(1):1–64, January 1997. [LW94] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994. [MS96] Lily Mummert and Mahadev Satyanarayanan. Long term distributed file reference tracing: Implementation and experience. Software - Practice and Experience (SPE), 26(6):705–736, June 1996.