Randomized and multipointer paging with locality of reference

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized and multipointer paging with locality of reference

Full text

Pdf (818 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 626 - 634

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Amos Fiat	Dept of Computer Science, Tel Aviv University, Tel Aviv, Israel
Anna R. Karlin	Dept of Computer Science, FR-35, University of Washington, Seattle, WA

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): 8, Citation Count: 14

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/225058.225280 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.

	1	L .A. Belady. A study of replacement algorithms for virtual storage computers. IBM SysterrM Jovr-nal, 5:78-101, 1966.
	2	Allan Borodin , Prabhakar Raghavan , Sandy Irani , Baruch Schieber, Competitive paging with locality of reference, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.249-259, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103422]
	3	P. J. Denning. Working sets past and present. IEEE Trans. Software Engg., SE-6:64--84, 198(1.
	4	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]
	5	P. A. Franaszek , T. J. Wagner, Some Distribution-Free Aspects of Paging Algorithm Performance, Journal of the ACM (JACM), v.21 n.1, p.31-39, Jan. 1974 [doi>10.1145/321796.321800]
	6	Kieran Harty , David R. Cheriton, Application-controlled physical memory using external page-cache management, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.187-197, October 12-15, 1992, Boston, Massachusetts, United States
	7	Sandy Irani , Anna R. Karlin , Steven Phillips, Strongly competitive algorithms for paging with locality of reference, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.228-236, September 1992, Orlando, Florida, United States
	8	A. R. Karlin, M. S. Manasse, L. Rudolph, and D.D. Sleator. Competitive snoopy caching. Algo-rithmtca, 3(1):70-119, 1988.
	9	A. R. Karlin, S. Phillips, and P. Raghavan. Markov paging. In Proceedings of $'t?rd Annual Symposiwm on Foundations of Computer Science, 1992.
	10	T. Kilburn, D.B. G. Edwards, M.J. Lanigan, and F.H. Sumner. One-level storage system. IRE Trans. Elect. Computers, 37:223-235, 1962.
	11	E. Koutsoupias and C. Papadirnitriou. Beyond competitive analysis. In Proceedings of 35rd An-nual Symposium on Foundations of Computer Science, 1994.
	12	C. Lund, S. Phillips and N. Reingold. IP-paging and distributional paging. In Proceedings of 35rd Annual Symposium on Foundations oj Computer Sc8ence, 1994.
	13	Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
	14	L.A. McGeoch and D.D. Sleator. A strongly com-petitive randomized paging algorithm. Algorith-mic, 6(6):816-825, 1991.
	15	D. McNamee and K. Armstrong. Extending the Mach external pager interface to aceomrnoclate user-level page replacement policies, In Pro-ceedings of the First USENIX Mach Symposium, 1990.
	16	Prabhakar Raghavan , Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.687-703, July 11-15, 1989
	17	G.S. Shedler and C. Tung. Locality in page ref-erence strings. SIAM Journal on Computing, 1:218-241, 1972.
	18	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]
	19	Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977
	20	AC. Yao. Probabilistic Computations: Towards a unifed measure of complexity. In Proceedings o~ the 18th Annual Symposium on Foundations of Computer Science, 1977.

CITED BY 14

	Virgil Andronache , Edwin H.-M. Sha , Nelson L. Passos, Design and analysis of efficient application-specific on-line page replacement techniques, Proceedings of the 10th Great Lakes symposium on VLSI, p.123-128, March 02-04, 2000, Chicago, Illinois, United States
	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
	Marek Chrobak , John Noga, LRU is better than FIFO, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.78-81, January 25-27, 1998, San Francisco, California, United States
	Susanne Albers , Naveen Garg , Stefano Leonardi, Minimizing stall time in single and parallel disk systems, Journal of the ACM (JACM), v.47 n.6, p.969-986, Nov. 2000
	Susanne Albers , Stefano Leonardi, On-line algorithms, ACM Computing Surveys (CSUR), v.31 n.3es, Sept. 1999
	Amos Fiat , Ziv Rosen, Experimental studies of access graph based heuristics: beating the LRU standard?, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.63-72, January 05-07, 1997, New Orleans, Louisiana, United States
	Mark Brehob , Richard Enbody , Eric Torng , Stephen Wagner, On-line restricted caching, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.374-383, January 07-09, 2001, Washington, D.C., United States
	Alexander Gaysinsky , Alon Itai , Hadas Shachnai, Strongly competitive algorithms for caching with pipelined prefetching, Information Processing Letters, v.91 n.1, p.19-27, 16 July 2004
	Ronny Lempel , Shlomo Moran, Competitive caching of query results in search engines, Theoretical Computer Science, v.324 n.2-3, p.253-271, 20 September 2004
	Mark Brehob , Richard Enbody , Eric Torng , Stephen Wagner, On-line restricted caching, Journal of Scheduling, v.6 n.2, p.149-166, March/April 2003
	Susanne Albers , Lene M. Favrholdt , Oliver Giel, On paging with locality of reference, Journal of Computer and System Sciences, v.70 n.2, p.145-175, March 2005
	Susanne Albers , Lene M. Favrholdt , Oliver Giel, On paging with locality of reference, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Susanne Albers , Naveen Garg , Stefano Leonardi, Minimizing stall time in single and parallel disk systems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.454-462, May 24-26, 1998, Dallas, Texas, United States
	Naveen Garg , Anupam Gupta , Stefano Leonardi , Piotr Sankowski, Stochastic analyses for online combinatorial optimization problems, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.942-951, January 20-22, 2008, San Francisco, California