{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T22:06:52Z","timestamp":1791238012093,"version":"4.1.0"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1978,8]]},"abstract":"<jats:p>In the independent reference model of program behavior, King\u2019s formulas for the expected FIFO (\u201cfirst-in-first-out\u201d) and expected LRU (\u201cleast-recently-used\u201d) miss ratios each contain an exponential number of terms (very roughly $n^{{\\text{CAP}}} $, where n is the number of pages and CAP is the capacity of main memory). Hence, under the straightforward algorithms, these formulas are computationally intractable. We present an algorithm which is both efficient (there are $O(n \\cdot {\\text{CAP}})$ additions, multiplications, and divisions) and provably numerically stable, for calculating the expected FIFO miss ratio. In the case of LRU, we present an efficient method, based on an urn model, for obtaining an unbiased estimate of the expected LRU miss ratio (the method requires $O(n \\cdot {\\text{CAP}})$ additions and comparisons, and $O({\\text{CAP}})$ divisions and random number generations).<\/jats:p>","DOI":"10.1137\/0207025","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:01:52Z","timestamp":1109224912000},"page":"288-297","source":"Crossref","is-referenced-by-count":29,"title":["Efficient Calculation of Expected Miss Ratios in the Independent Reference Model"],"prefix":"10.1137","volume":"7","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas G.","family":"Price","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321632"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.1674682"},{"key":"R3","unstructured":"F. Baskett, A. Rafii,  The A0 inversion model of program paging behavior,  1976, Computer Science Rep. CS-76-579, Stanford University, Nov., Comm. ACM, to appear."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/361268.361281"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1147\/rd.196.0550"},{"key":"R7A","doi-asserted-by":"publisher","DOI":"10.1145\/359997.360012"},{"key":"R7B","doi-asserted-by":"publisher","DOI":"10.1145\/359997.360012"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80014-7"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321935"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321800"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1973.5009115"},{"key":"R12","volume-title":"Inequalities","author":"Hardy G. H.","year":"1964"},{"key":"R13","unstructured":"W. F. King, III,  Analysis of paging algorithms,  IFIP Conf. Proc. Ljubljana, Yugoslavia,  1971, Aug. 0254.68010"},{"key":"R14A","volume-title":"The art of computer programming. Vol. 2: Seminumerical algorithms","author":"Knuth Donald E.","year":"1969"},{"key":"R14B","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1147\/rd.172.0086"},{"key":"R16","unstructured":"P. A. Lewis, P. C. Yue,  Statistical analysis of program reference patterns in a paging environment,  Proc. IEEE Conf. Computers, Boston,  1971"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/360051.360227"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1147\/sj.92.0078"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/361532.361554"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/360051.360231"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/C-M.1976.218434"},{"key":"R22","volume-title":"A relation between working set and optimal algorithms for segment reference strings","author":"Slutz D. R.","year":"1975"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"J. R. Spirn, P. J. Denning,  Experiments with program locality,  AFIPS Conf. Proc. 41,  1972,  611\u2013621","DOI":"10.1145\/1479992.1480078"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/321784.321790"},{"key":"R25","volume-title":"Human Behavior and the Principle of Least Effort","author":"Zipf G. K.","year":"1949"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0207025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:01Z","timestamp":1787337001000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0207025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1978,8]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1978,8]]}},"alternative-id":["10.1137\/0207025"],"URL":"https:\/\/doi.org\/10.1137\/0207025","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1978,8]]}}}