SC17 Denver, CO

P12: Multi-Size Optional Offline Caching Algorithms

Authors: Andrew Y. Choliy (Rutgers University), Max D. Whitmore (Brandeis University), Gruia Calinescu (Illinois Institute of Technology)

Abstract: The 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.
Award: Best Poster Finalist (BP): no

Poster: pdf
Two-page extended abstract: pdf

Poster Index