{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:33:14Z","timestamp":1750307594367,"version":"3.41.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,1,25]],"date-time":"2010-01-25T00:00:00Z","timestamp":1264377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2010,1,25]]},"abstract":"<jats:p>As computer science has progressed, numerous models and measures have been developed over the years. Among the most commonly used in theoretical computer science are the RAM model, the I\/O model, worst case analysis, space (memory) usage, average case analysis, amortized analysis, adaptive analysis and the competitive ratio. New models are added to this list every few years to re ect varying constraints imposed by novel application or advances in computer architectures. Examples of alternative models are the transdichotomous RAM or word-RAM, the data stream model, the MapReduce model, the cache oblivious model and the smoothed analysis model. New models and measures, when successful expand our understanding of computation and open new avenues of inquiry. As it is to be expected relatively few models and paradigms are introduced every year, and even less are eventually proven successful. In this paper we discuss rst certain shortcomings of the online competitive analysis model particularly as it concerns paging, discuss existing solutions in the literature as well as present recent progress in developing models and measures that better re ect actual practice for the case of paging. From there we proceed to a more general discussion on how to measure and evaluate new models within theoretical computer science and how to contrast them, when appropriate, to existing models. Lastly, we highlight certain \\natural\" choices and assumptions of the standard worst-case model which are often unstated and rarely explicitly justied. We contrast these choices to those made in the formalization of probability theory.<\/jats:p>","DOI":"10.1145\/1711475.1714372","type":"journal-article","created":{"date-parts":[[2012,10,15]],"date-time":"2012-10-15T19:22:23Z","timestamp":1350328943000},"page":"98-123","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On Developing New Models, with Paging as a Case Study"],"prefix":"10.1145","volume":"40","author":[{"given":"Reza","family":"Dorrigiv","sequence":"first","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, Ont., N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science University of Waterloo, Waterloo, Ont., N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,25]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"229","volume-title":"Proc. SODA","author":"Angelopoulos S.","year":"2007"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792918.1792953"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.08.002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_9"},{"volume-title":"AAAI","year":"2008","author":"Angelopoulos Spyros","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496893"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"volume-title":"Empirical model-building and response surface","year":"1986","author":"Box G. E. P.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294264"},{"key":"e_1_2_1_10_1","first-page":"98","volume-title":"Proc. ESA","author":"Becchetti L.","year":"2004"},{"key":"e_1_2_1_11_1","first-page":"53","volume-title":"Proc. SODA","author":"Bachrach R.","year":"1997"},{"volume-title":"Online Computation and Competitive Analysis","year":"1998","author":"Borodin A.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1757536.1757552"},{"key":"e_1_2_1_14_1","first-page":"718","volume-title":"Proc. SODA","author":"Boyar J.","year":"2005"},{"key":"e_1_2_1_15_1","first-page":"137","volume-title":"CCCG","author":"Biedl Therese C.","year":"2002"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1021"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009286"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361786"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009255"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12450-1_10"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363141"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1980.230464"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1070838.1070856"},{"key":"e_1_2_1_25_1","first-page":"32","volume-title":"Proc. 6th ISAAC","author":"Datta A.","year":"1995"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086649.1086670"},{"key":"e_1_2_1_28_1","first-page":"215","volume-title":"Proc. CCCG","author":"Dorrigiv R.","year":"2008"},{"key":"e_1_2_1_29_1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BFb0029578","volume-title":"Online Algorithms -- The State of the Art","author":"Fiat A.","year":"1998"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/5505.5507"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799348670"},{"volume-title":"Dissertation","year":"1994","author":"Icking Ch.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","first-page":"443","volume-title":"CCCG","author":"Icking Christian","year":"1993"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236353"},{"key":"e_1_2_1_35_1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/BFb0029564","volume-title":"Online Algorithms -- The State of the Art","author":"Irani S.","year":"1998"},{"key":"e_1_2_1_36_1","first-page":"359","volume-title":"Proc. SODA","author":"Kenyon C.","year":"1996"},{"key":"e_1_2_1_37_1","first-page":"372","volume-title":"Proc. 5th SODA","author":"Kao M.-Y.","year":"1994"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796299540"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268042"},{"key":"e_1_2_1_40_1","first-page":"441","volume-title":"Proc. 4th SODA","author":"Kao M.-Y.","year":"1993"},{"key":"e_1_2_1_41_1","unstructured":"{Kru} P. Krugman. How i work. Available at: http:\/\/web.mit.edu\/krugman\/www\/howiwork.html.  {Kru} P. Krugman. How i work. Available at: http:\/\/web.mit.edu\/krugman\/www\/howiwork.html."},{"volume-title":"AAAI","year":"2006","author":"L\u00f3pez-Ortiz Alejandro","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/645898.672283"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00144-4"},{"key":"e_1_2_1_46_1","first-page":"125","volume-title":"CCCG","author":"L\u00f3pez-Ortiz Alejandro","year":"2001"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/645901.672766"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.08.001"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542412"},{"volume-title":"Cache-oblivious algorithms. Master's thesis","year":"1999","author":"Prokop H.","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132587"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800180202"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294261"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/646341.686576"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009192"},{"key":"e_1_2_1_58_1","unstructured":"{Uni} New Mexico State University. Homepage of new mexico state university tracebase (online). Available at: http:\/\/tracebase.nmsu.edu\/tracebase.html.  {Uni} New Mexico State University. Homepage of new mexico state university tracebase (online). Available at: http:\/\/tracebase.nmsu.edu\/tracebase.html."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_2_1_60_1","first-page":"420","volume-title":"Proc. SODA","author":"Young N. E.","year":"1998"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1099"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0124-5"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1711475.1714372","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1711475.1714372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:35Z","timestamp":1750250495000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1711475.1714372"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,25]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1,25]]}},"alternative-id":["10.1145\/1711475.1714372"],"URL":"https:\/\/doi.org\/10.1145\/1711475.1714372","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2010,1,25]]},"assertion":[{"value":"2010-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}