CSP Seminar

Accurate Learning or Fast Mixing? Dynamic Adaptability of Caching Algorithms

Vijay Subramanian

Associate Professor
University of Michigan
Thursday, January 25, 2018
4:00pm - 5:00pm
1005 EECS

Add to Google Calendar

About the Event

Typical analysis of content caching algorithms using the metric of hit probability under a stationary request process does not account for performance loss under a variable request arrival process. In this work, we consider adaptability of caching algorithms from two perspectives: (a) the accuracy of learning a fixed popularity distribution; and (b) the speed of learning items' popularity. In order to attain this goal, we compute the distance between the stationary distributions of several popular algorithms with that of a genie-aided algorithm that has knowledge of the true popularity ranking, which we use as a measure of learning accuracy. We then characterize the mixing time of each algorithm, i.e., the time needed to attain the stationary distribution, which we use as a measure of learning efficiency. We merge both measures above to obtain the "learning error" representing both how quickly and how accurately an algorithm learns the optimal caching distribution, and use this to determine the trade-off between these two objectives of many popular caching algorithms. Informed by the results of our analysis, we propose a novel hybrid algorithm, Adaptive-LRU (A-LRU), that learns both faster and better the changes in the popularity. We show numerically that it also outperforms all other candidate algorithms when confronted with either a dynamically changing synthetic request process or using real world traces. This is joint work with Jian Li (UMass, Amherst), John C.S. Lui (CUHK) and Srinivas Shakkottai (TAMU) and is based on .


I am an Associate Professor in the EECS department at the University of Michigan. After graduating I worked in the research arm of the Networks Business Sector of Motorola in Arlington Heights, Illinois, USA until May 2006. In May 2006 I returned to an academic setting. I started with a move to the Hamilton Institute of the National University of Ireland, Maynooth as a Research Fellow. In the summer of 2010 I was a visiting researcher at LIDS MIT. From November 2010 to October 2011, I was a Senior Research Associate in the EECS Department at Northwestern University. From November 2011 until August 2014 I was a Research Assistant Professor in the EECS Department at Northwestern University.

Additional Information

Contact: Judi Jones

Phone: 763-8557


Sponsor(s): ECE - Systems

Faculty Sponsor: Dave Neuhoff

Open to: Public