ICS Theory Group

ICS 269, Fall 2004: Theory Seminar

19 Nov 2004:
Caching with Expiration Times
Authors: Parikshit Gopalan , Howard Karloff , Aranyak Mehta , Milena Mihail , Nisheeth Vishnoi
Speaker: Michael Shindler

From: Proceedings 13th ACM-SIAM Symp. on Discrete Algorithms (SODA), January 6-8, 2002, San Francisco, pp.540-547.

The authors investigate the effects of caching when dealing with both access frequency and expiration times, using the common least-recently used algorithm as a starting point. They present and analyze three different classes of algorithms for dealing with the problem. There exist deterministic marking algorithms that are competitive relative to the size of the cache. They also discuss randomized marking algorithms and the optimal offline algorithm.