P12: Multi-Size Optional Offline Caching Algorithms
SessionPoster Reception
Event Type
ACM Student Research Competition
Poster
Reception
TimeTuesday, November 14th5:15pm -
7pm
LocationFour Seasons Ballroom
DescriptionThe optional offline caching (paging) problem, where
all future file requests are known, is a variant of the
heavily studied online caching problem. This offline
problem has applications in web caching and distributed
storage systems. Given a set of unique files with
varying sizes, a series of requests for these files,
fast cache memory of limited size, and slow main memory,
an efficient replacement policy is necessary to decide
when it is best to evict some file(s) from the cache in
favor of another. It is known that this problem is
NP-complete, and few approximation algorithms have been
proposed. We propose three new heuristics, as well as a
4-approximation algorithm. We then evaluate each
algorithm by the metrics of runtime complexity and
proximity to the optimal solutions of many synthetic
data sets.
