BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-00-94
       ENTRY:: May 15, 2000
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Web Caching using Access Statistics
        TYPE:: Technical Note
      AUTHOR:: Meyerson, Adam
      AUTHOR:: Munagala, Kamesh
      AUTHOR:: Plotkin, Serge
        DATE:: May 2000
       PAGES:: 15
    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.
       NOTES:: [Adminitrivia V1/Prg/20000515]
         END:: STAN//CS-TN-00-94