Report Number: CS-TN-00-94
Institution: Stanford University, Department of Computer Science
Title: Web Caching using Access Statistics
Author: Meyerson, Adam
Author: Munagala, Kamesh
Author: Plotkin, Serge
Date: May 2000
Abstract: We present the problem of caching web pages under the assumption that each user has a fixed, known demand vector for the pages. Such demands could be computed using access statistics. We wish to place web pages in the caches in order to optimize the latency from user to page, under the constraints that each cache has limited memory and can support a limited total number of requests. When C caches are present with fixed locations, we present a constant factor approximation to the latency while exceeding capacity constraints by log C. We improve this result to a constant factor provided no replication of web pages is allowed. We present a constant factor approximation where the goal is to minimize the maximum latency. We also consider the case where we can place our own caches in the network for a cost, and produce a constant approximation to the sum of cache cost plus weighted average latency. Finally, we extend our results to incorporate page update latency, temporal variation in request rates, and economies of scale in cache costs.