{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:58:17Z","timestamp":1725566297344},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230250"},{"type":"electronic","value":"9783540301400"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30140-0_11","type":"book-chapter","created":{"date-parts":[[2010,9,19]],"date-time":"2010-09-19T01:31:13Z","timestamp":1284859873000},"page":"98-109","source":"Crossref","is-referenced-by-count":20,"title":["Modeling Locality: A Probabilistic Analysis of LRU and FWF"],"prefix":"10.1007","author":[{"given":"Luca","family":"Becchetti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Albers, S., Favrholdt, L.M., Giel, O.: On paging with locality of reference. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 258\u2013267 (2002)","DOI":"10.1145\/509907.509949"},{"issue":"2","key":"11_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"L.A. Belady","year":"1966","unstructured":"Belady, L.A.: A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal\u00a05(2), 78\u2013101 (1966)","journal-title":"IBM Systems Journal"},{"key":"11_CR3","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 249\u2013259 (1991)","DOI":"10.1145\/103418.103422"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst case order ratio applied to paging. In: Proceedings of the 5th Italian Conference on Algorithms and Complexity, pp. 58\u201369 (2003)","DOI":"10.1007\/3-540-44849-7_13"},{"key":"11_CR6","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst order ratio applied to paging. Tech. report ALCOMFT-TR-03-32, Future and Emerging Technologies program under the EU, contract number IST-1999-14186 (2003)"},{"issue":"5","key":"11_CR7","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1145\/363095.363141","volume":"11","author":"P.J. Denning","year":"1968","unstructured":"Denning, P.J.: The working set model for program behaviour. Communications of the ACM\u00a011(5), 323\u2013333 (1968)","journal-title":"Communications of the ACM"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Fiat, A., Karlin, A.R.: Randomized and multipointer paging with locality of reference. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pp. 626\u2013634 (1995)","DOI":"10.1145\/225058.225280"},{"issue":"4","key":"11_CR9","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A. Fiat","year":"1991","unstructured":"Fiat, A., Karp, R., Luby, M., McGeoch, L., Sleator, D., Young, N.E.: Competitive paging algorithms. Journal of Algorithms\u00a012(4), 685\u2013699 (1991)","journal-title":"Journal of Algorithms"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Fiat, A., Mendel, M.: Truly online paging with locality of reference. In: 38th IEEE Annual Symposium on Foundations of Computer Science, pp. 326\u2013335 (1997)","DOI":"10.1109\/SFCS.1997.646121"},{"issue":"3","key":"11_CR11","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/S0097539792236353","volume":"25","author":"S. Irani","year":"1996","unstructured":"Irani, S., Karlin, A.R., Phillips, S.: Strongly competitive algorithms for paging with locality of reference. SIAM Journal on Computing\u00a025(3), 477\u2013497 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Karlin, R., Phillips, S.J., Raghavan, P.: Markov paging. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pp. 208\u2013217 (1992)","DOI":"10.1109\/SFCS.1992.267771"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 394\u2013400 (1994)","DOI":"10.1109\/SFCS.1994.365677"},{"key":"11_CR14","unstructured":"Chrobak, M., Noga, J.: LRU is better than FIFO. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 78\u201381 (1998)"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"Sleator, D., Tarjan, R.E.: Amortized Efficiency of List Update and Paging Rules. Communications of the ACM\u00a028, 202\u2013208 (1985)","journal-title":"Communications of the ACM"},{"key":"11_CR16","volume-title":"Modern Operating Systems","author":"A.S. Tanenbaum","year":"1992","unstructured":"Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall, Englewood Cliffs (1992)"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Torng, E.: A unified analysis of paging and caching. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 194\u2013203 (1995)","DOI":"10.1109\/SFCS.1995.492476"},{"issue":"6","key":"11_CR18","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"N. Young","year":"1994","unstructured":"Young, N.: The k-server dual and loose competitiveness for paging. Algorithmica\u00a011(6), 525\u2013541 (1994)","journal-title":"Algorithmica"},{"key":"11_CR19","unstructured":"Young, N.E.: On-line file caching. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 82\u201386 (1998)"},{"issue":"1","key":"11_CR20","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1006\/jagm.2000.1099","volume":"37","author":"N.E. Young","year":"2000","unstructured":"Young, N.E.: On-line paging against adversarially biased random inputs. Journal of Algorithms\u00a037(1), 218\u2013235 (2000)","journal-title":"Journal of Algorithms"},{"key":"11_CR21","unstructured":"Young, N.: Competitive paging and dual-guided on-line weighted caching and matching algorithms. PhD thesis, Department of Computer Science, Princeton University (1991)"},{"key":"11_CR22","unstructured":"Young, N.E.: Bounding the diffuse adversary. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 420\u2013425 (1998)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30140-0_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:52:04Z","timestamp":1620013924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30140-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230250","9783540301400"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30140-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}