Skip to main content
Journal cover image

Web caching using access statistics

Publication ,  Conference
Meyerson, A; Munagala, K; Plotkin, S
Published in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
December 1, 2001

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 Scholars

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

ISBN

0898714907

Publication Date

December 1, 2001

Start / End Page

354 / 363
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Meyerson, A., Munagala, K., & Plotkin, S. (2001). Web caching using access statistics. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 354–363).
Meyerson, A., K. Munagala, and S. Plotkin. “Web caching using access statistics.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 354–63, 2001.
Meyerson A, Munagala K, Plotkin S. Web caching using access statistics. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 354–63.
Meyerson, A., et al. “Web caching using access statistics.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 354–63.
Meyerson A, Munagala K, Plotkin S. Web caching using access statistics. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 354–363.
Journal cover image

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

ISBN

0898714907

Publication Date

December 1, 2001

Start / End Page

354 / 363