{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:24Z","timestamp":1787337504479,"version":"build-2736575974"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Response time delays caused by I\/O are a major problem in many systems and database applications. Prefetching and cache replacement methods are attracting renewed attention because of their success in avoiding costly I\/Os. Prefetching can be looked upon as a type of online sequential prediction, where the predictions must be accurate as well as made in a computationally efficient way. Unlike other online problems, prefetching cannot admit a competitive analysis, since the optimal offline prefetcher incurs no cost when it knows the future page requests. Previous analytical work on prefetching [. Vitter Krishnan 1991.] [J. Assoc. Comput. Mach., 143 (1996), pp. 771--793] consisted of modeling the user as a probabilistic Markov source.<\/jats:p>\n                  <jats:p>In this paper, we look at the much stronger form of worst-case analysis and derive a randomized algorithm for pure prefetching. We compare our algorithm for every page request sequence with the important class of finite state prefetchers, making no assumptions as to how the sequence of page requests is generated. We prove analytically that the fault rate of our online prefetching algorithm converges almost surely for every page request sequence to the fault rate of the optimal finite state prefetcher for the sequence. This analysis model can be looked upon as a generalization of the competitive framework, in that it compares an online algorithm in a worst-case manner over all sequences with a powerful yet nonclairvoyant opponent. We simultaneously achieve the computational goal of implementing our prefetcher in optimal constant expected time per prefetched page using the optimal dynamic discrete random variate generator of [. Matias Matias, Vitter, and Ni [Proc. 4th Annual SIAM\/ACM Symposium on Discrete Algorithms, Austin, TX, January 1993].<\/jats:p>","DOI":"10.1137\/s0097539794261817","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1617-1636","source":"Crossref","is-referenced-by-count":24,"title":["Optimal Prediction for Prefetching in the Worst Case"],"prefix":"10.1137","volume":"27","author":[{"given":"P.","family":"Krishnan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"D. Aldous and U. Vazirani,\n                      A Markovian extension of Valiant\u2019s learning model\n                      , in Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, October 1990, pp. 392\u2013396.","DOI":"10.1109\/FSCS.1990.89558"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/18.179348"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1021"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"T. F. Chen and J. L. Baer,\n                      Reducing memory latency via non\u2010blocking and prefetching caches\n                      , in Proc. 5th Internat. Conf. on Architectural Support for Programming Languages and Operating Systems, Department of Computer Science and Engineering, University of Washington, Boston, MA, October 1992.","DOI":"10.1145\/143365.143486"},{"key":"R7","unstructured":"T. M. Cover,\n                      Behavior of predictors of binary sequences\n                      , in Proc. 4th Prague Conference on Information Theory, Statistical Decision Functions, Random Processes, Publishing House of the Czechoslovak Academy of Sciences, Prague, 1967, pp. 263\u2013272."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1977.4309738"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"K. Curewitz, P. Krishnan, and J. S. Vitter,\n                      Practical prefetching via data compression\n                      , in Proc. 1993 ACM SIGMOD International Conference on Management of Data, May 1993, pp. 257\u2013266.","DOI":"10.1145\/170035.170077"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1980.230464"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/18.144706"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"R14","unstructured":"R. G. Gallager,\n                      Information Theory and Reliable Communication\n                      , Wiley, New York, 1968."},{"key":"R15","unstructured":"Ronald Graham, Donald Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warsaw, 1998, 719\u20130, Translated from the second English (1994) edition by P. Chrz\u0105stowski, A. Czumaj, L. G\u0105sieniec and M. Raczunas99m:68002"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"T. Hagerup, K. Mehlhorn, and I. Munro,\n                      Optimal algorithms for generating time varying discrete random variables\n                      , in Proc. of the 20th Annual International Coll. on Automata Languages and Prog., Lecture Notes in Comput. Sci. 700, Springer, New York, 1993, pp. 253\u2013264.","DOI":"10.1007\/3-540-56939-1_77"},{"key":"R17","unstructured":"James Hannan, Approximation to Bayes risk in repeated play, Annals of Mathematics Studies, no. 39, Princeton University Press, Princeton, N. J., 1957, 97\u201313921:7806"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(92)90066-9"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236353"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. R. Karlin, S. J. Phillips, and P. Raghavan,\n                      Markov paging\n                      , in Proc. 33rd Annual IEEE Conference on Foundations of Computer Science, October 1992, pp. 208\u2013217.","DOI":"10.1109\/SFCS.1992.267771"},{"key":"R21","volume-title":"The art of computer programming. Vol. 2","author":"Knuth Donald","year":"1981"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"D. F. Kotz and C. S. Ellis,\n                      Prefetching in File Systems for MIMD Multiprocessors\n                      , IEEE Transactions on Parallel and Distributed Systems, Vol. 1, April 1990, pp. 218\u2013230.","DOI":"10.1109\/71.80133"},{"key":"R23","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1137\/S0097539794261817","volume":"27","author":"Krishnan P.","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R24","unstructured":"P. Laird,\n                      TDAG: An Algorithm for Learning to Predict Discrete Sequences\n                      , FIA\u201092\u201001, NASA Ames Research Center, AI Research Branch, Moffet Field, CA, 1992."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"G. G. Langdon,\n                      A Note on the Ziv\u2013Lempel Model for Compressing Individual Sequences\n                      , IEEE Trans. Inform. Theory, Vol. 29, March 1983, pp. 284\u2013287.","DOI":"10.1109\/TIT.1983.1056645"},{"key":"R26","unstructured":"Yossi Matias, Jeffrey Vitter, Wen Ni, Dynamic generation of discrete random variates, ACM, New York, 1993, 361\u201337094d:65009"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"N. Merhav and M. Feder,\n                      Universal Sequential Learning and Decision from Individual Data Sequences\n                      , in Proc. 5th ACM Workshop on Computational Learning Theory, Santa Cruz, July 1992.","DOI":"10.1145\/130385.130430"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"T. C. Mowry, M. S. Lam, and A. Gupta,\n                      Design and evaluation of a compiler algorithm for prefetching\n                      , in Proc. 5th International Conference on Architectural Support for Programming Languages and Operating Systems Computer Systems Laboratory, Boston, MA, October 1992.","DOI":"10.1145\/143365.143488"},{"key":"R30","unstructured":"M. Palmer and S. Zdonik,\n                      Fido: A cache that learns to fetch\n                      , in Proc. 1991 International Conference on Very Large Databases, Barcelona, September 1991."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"A. Rogers and K. Li,\n                      Software support for speculative loads\n                      , in Proc. 5th International Conference on Architectural Support for Programming Languages and Operating Systems, Department of Computer Science, Boston, MA, October 1992.","DOI":"10.1145\/143365.143484"},{"key":"R32","unstructured":"K. Salem,\n                      Adaptive Prefetching for Disk Buffers\n                      , CESDIS, Goddard Space Flight Center, Greenbelt, MD, TR\u201391\u201346, January 1991."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0201016"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R35","unstructured":"J. S. Vitter, K. Curewitz, and P. Krishnan,\n                      Online Background Predictors and Prefetchers\n                      , Duke University, United States Patent No. 5,485,609, January 16, 1996."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1145\/234752.234753"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794261817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:16Z","timestamp":1787336056000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794261817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794261817"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794261817","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}