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.
http://i.stanford.edu/pub/cstr/reports/cs/tn/00/94/CS-TN-00-94.pdf