Page replacement with multi-size pages and applications to Web caching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Page replacement with multi-size pages and applications to Web caching

Full text

Pdf (1.26 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 701 - 710

Year of Publication: 1997

ISBN:0-89791-888-6

Author

Sandy Irani

Information and Computer Science Department, University of California, Irvine, Irvine, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 26, Citation Count: 24

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/258533.258666 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AW96	Martin F. Arlitt , Carey L. Williamson, Web server workload characterization: the search for invariants, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.126-137, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/233013.233034]
	Bel66	L.A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78-101, 1966.
	BCC+95	A. Bestavros , R. L. Carter , M. E. Crovella , C. R. Cunha , A. Heddaya , S. A. Mirdad, Application-level document caching in the Internet, Proceedings of the 2nd International Workshop on Services in Distributed and Networked Environments, p.166, June 05-08, 1995
	DHS93	Peter B. Danzig , Richard S. Hall , Michael F. Schwartz, A case for caching file objects inside internetworks, Conference proceedings on Communications architectures, protocols and applications, p.239-248, September 13-17, 1993, San Francisco, California, United States [doi>10.1145/166237.166260]
	FKIP96	A. Feldman, A. Karlin, S. Irani, S. Phillips. Private Communication.
	FKL+91	Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
	KMR95	Thomas T. Kwan , Robert E. McGrath , Daniel A. Reed, NCSA's World Wide Web Server: Design and Performance, Computer, v.28 n.11, p.68-74, November 1995 [doi>10.1109/2.471181]
	LPR94	C. Lund, S. Phillips, and N. Reingold. Ip over connection-oriented networks and distributional paging. In 35ih iEEE Symposium on Foundations of Computer Science, pages 424-435, 1994.
	M96	Evangelos P. Markatos, Main memory caching of Web documents, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.893-905, May 1996, Paris, France
	ST85	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	WAS+96	Marc Abrams , Charles R. Standridge , Ghaleb Abdulla , Edward A. Fox , Stephen Williams, Removal policies in network caches for World-Wide Web documents, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.293-305, August 28-30, 1996, Palo Alto, California, United States [doi>10.1145/248156.248182]

CITED BY 24

	Edith Cohen , Haim Kaplan, LP-based analysis of greedy-dual-size, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.879-880, January 17-19, 1999, Baltimore, Maryland, United States
	Parikshit Gopalan , Howard Karloff , Aranyak Mehta , Milena Mihail , Nisheeth Vishnoi, Caching with expiration times, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.540-547, January 06-08, 2002, San Francisco, California
	Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Placement algorithms for hierarchical cooperative caching, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.586-595, January 17-19, 1999, Baltimore, Maryland, United States
	Hiroshi Kawazoe , Tetsuo Shibuya , Takeshi Tokuyama, Optimal on-line algorithms for an electronic commerce money distribution system, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.527-536, January 17-19, 1999, Baltimore, Maryland, United States
	Tracy Kimbrel, Online paging and file caching with expiration times, Theoretical Computer Science, v.268 n.1, p.119-131, 10/06/2001
	Neal E. Young, On-line file caching, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.82-86, January 25-27, 1998, San Francisco, California, United States
	Edith Cohen , Haim Kaplan, Exploiting regularities in Web traffic patterns for cache replacement, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.109-118, May 01-04, 1999, Atlanta, Georgia, United States
	Friedhelm Meyer auf der Heide , Berthold Vöcking , Matthias Westermann, Caching in networks (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.430-439, January 09-11, 2000, San Francisco, California, United States
	Susanne Albers , Sanjeev Arora , Sanjeev Khanna, Page replacement for general caching problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.31-40, January 17-19, 1999, Baltimore, Maryland, United States
	Akshat Verma , Sugata Ghosal, On admission control for profit maximization of networked service providers, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
	Edith Cohen , Haim Kaplan , Uri Zwick, Connection caching, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.612-621, May 01-04, 1999, Atlanta, Georgia, United States
	Edith Cohen , Haim Kaplan , Uri Zwick, Connection caching: model and algorithms, Journal of Computer and System Sciences, v.67 n.1, p.92-126, August 2003
	Adam Meyerson , Kamesh Munagala , Serge Plotkin, Web caching using access statistics, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.354-363, January 07-09, 2001, Washington, D.C., United States
	Susanne Albers, New results on web caching with request reordering, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Rudolf Fleischer , Włodzimierz Głazek , Steve Seiden, New results for online page replication, Theoretical Computer Science, v.324 n.2-3, p.219-251, 20 September 2004
	Jun Kiniwa , Toshio Hamada , Daisuke Mizoguchi, Lookahead Scheduling Requests for Multisize Page Caching, IEEE Transactions on Computers, v.50 n.9, p.972-983, September 2001
	Saied Hosseini-Khayat, On Optimal Replacement of Nonuniform Cache Objects, IEEE Transactions on Computers, v.49 n.8, p.769-778, August 2000
	Madhukar R. Korupolu , Michael Dahlin, Coordinated Placement and Replacement for Large-Scale Distributed Caches, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1317-1329, November 2002
	Alejandro López-Ortiz, Algorithmic foundations of the internet, ACM SIGACT News, v.36 n.2, June 2005
	Leah Epstein , Yanir Kleiman , Jií Sgall , Rob van Stee, Paging with connections: FIFO strikes again, Theoretical Computer Science, v.377 n.1-3, p.55-64, May, 2007
	Pei Cao , Sandy Irani, Cost-aware WWW proxy caching algorithms, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.18-18, December 08-11, 1997, Monterey, California
	Kim Hazelwood , Michael D. Smith, Generational Cache Management of Code Traces in Dynamic Optimization Systems, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.169, December 03-05, 2003
	Nikhil Bansal , Niv Buchbinder , Joseph (Seffi) Naor, Randomized competitive algorithms for generalized caching, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Niv Buchbinder , Joseph (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal: Dual Approach, Foundations and Trends® in Theoretical Computer Science, v.3 n.2$#8211;3, p.93-263, February 2009