Web caching using access statistics

Conference Paper

We consider the problem of caching web pages with the objective of minimizing latency of access. Demands for web domains/pages are computed using access statistics; the frequency with which these statistics change is considerably longer than the frequency of page requests. We model caches as being constrained by total size and total number of ports: each cache can handle only a limited request rate and can store only a limited number of domains (eg. modelling bounded update traffic). When the caches have fixed locations, we present a constant factor approximation to the optimum average latency while exceeding capacity constraints by a logarithmic factor. We demonstrate improved results in the special case where no replication of pages is allowed. In the alternate model where we are allowed to place our own caches in the network for a cost, we produce a constant approximation to the weighted sum of cost and average latency. Finally, we consider several other variants of the problem which might arise in practice. Copyright © 2009 ACM, Inc.

Duke Authors

Cited Authors

  • Meyerson, A; Munagala, K; Plotkin, S

Published Date

  • December 1, 2001

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 354 - 363

International Standard Book Number 10 (ISBN-10)

  • 0898714907

Citation Source

  • Scopus