{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T01:44:02Z","timestamp":1768441442383,"version":"3.49.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2-4","license":[{"start":{"date-parts":[[2022,11,26]],"date-time":"2022-11-26T00:00:00Z","timestamp":1669420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"U.S. Army Research Laboratory and the U.K. Defence Science and Technology Laboratory","award":["W911NF-16-3-0001"],"award-info":[{"award-number":["W911NF-16-3-0001"]}]},{"name":"NSF","award":["CNS-1617437"],"award-info":[{"award-number":["CNS-1617437"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Caching systems have long been crucial for improving the performance of a wide variety of network and web-based online applications. In such systems, end-to-end application performance heavily depends on the fraction of objects transferred from the cache, also known as the\n            <jats:italic>cache hit probability<\/jats:italic>\n            . Many caching policies have been proposed and implemented to improve the hit probability. In this work, we propose a new method to compute an upper bound on hit probability for all non-anticipative caching policies and for policies that have no knowledge of future requests. Our key insight is to order the objects according to the ratio of their\n            <jats:italic>\n              <jats:bold>Hazard Rate<\/jats:bold>\n            <\/jats:italic>\n            <jats:bold>(HR)<\/jats:bold>\n            function values to their sizes, and place in the cache the objects with the largest ratios till the cache capacity is exhausted. When object request processes are conditionally independent, we prove that this cache allocation based on the HR-to-size ratio rule guarantees the maximum achievable expected number of object hits across all non-anticipative caching policies. Further, the HR ordering rule serves as an upper bound on cache hit probability when object request processes follow either independent delayed renewal process or a Markov modulated Poisson process. We also derive closed form expressions for the upper bound under some specific object request arrival processes. We provide simulation results to validate its correctness and to compare it to the state-of-the-art upper bounds, such as produced by B\u00e9l\u00e1dy\u2019s algorithm. We find it to be tighter than state-of-the-art upper bounds for some specific object request arrival processes such as independent renewal, Markov modulated, and shot noise processes.\n          <\/jats:p>","DOI":"10.1145\/3547332","type":"journal-article","created":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T11:29:41Z","timestamp":1657538981000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A New Upper Bound on Cache Hit Probability for Non-Anticipative Caching Policies"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9859-6794","authenticated-orcid":false,"given":"Nitish K.","family":"Panigrahy","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3186-0842","authenticated-orcid":false,"given":"Philippe","family":"Nain","sequence":"additional","affiliation":[{"name":"Centre Inria at Universit\u00e9 C\u00f4te d\u2019Azur, Sophia Antipolis Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8779-0620","authenticated-orcid":false,"given":"Giovanni","family":"Neglia","sequence":"additional","affiliation":[{"name":"Centre Inria at Universit\u00e9 C\u00f4te d\u2019Azur, Sophia Antipolis Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7808-7375","authenticated-orcid":false,"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,26]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/903516"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321632"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/pdis.1996.568672"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(95)00079-8"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/346000.346003"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-5316(99)00062-0"},{"key":"e_1_3_3_8_2","volume-title":"3rd USENIX Conference on File and Storage Technologies (FAST 04)","author":"Bansal Sorav","year":"2004","unstructured":"Sorav Bansal and Dharmendra S. Modha. 2004. CAR: Clock with adaptive replacement. In 3rd USENIX Conference on File and Storage Technologies (FAST 04). USENIX Association, San Francisco, CA. https:\/\/www.usenix.org\/conference\/fast-04\/car-clock-adaptive-replacement."},{"key":"e_1_3_3_9_2","first-page":"389","volume-title":"NSDI\u201918","author":"Beckmann Nathan","year":"2018","unstructured":"Nathan Beckmann, Haoxian Chen, and Asaf Cidon. 2018. LHD: Improving cache hit rate by maximizing hit density relative size. In NSDI\u201918. 389\u2013404."},{"issue":"2","key":"e_1_3_3_10_2","first-page":"1","article-title":"Practical bounds on optimal caching with variable object sizes","volume":"2","author":"Berger Daniel S.","year":"2018","unstructured":"Daniel S. Berger, Nathan Beckmann, and Mor Harchol-Balter. 2018. Practical bounds on optimal caching with variable object sizes. POMACS 2, 2 (2018), 1\u201332.","journal-title":"POMACS"},{"key":"e_1_3_3_11_2","first-page":"483","volume-title":"NSDI\u201917","author":"Berger Daniel S.","year":"2017","unstructured":"Daniel S. Berger, Ramesh K. Sitaraman, and Mor Harchol-Balter. 2017. AdaptSize: Orchestrating the hot object memory cache in a content delivery network. In NSDI\u201917. 483\u2013498."},{"key":"e_1_3_3_12_2","first-page":"499","volume-title":"2017 USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Blankstein Aaron","year":"2017","unstructured":"Aaron Blankstein, Siddhartha Sen, and Michael J. Freedman. 2017. Hyperbolic caching: Flexible caching for web applications. In 2017 USENIX Annual Technical Conference (USENIX ATC\u201917). USENIX Association, Santa Clara, CA, 499\u2013511. https:\/\/www.usenix.org\/conference\/atc17\/technical-sessions\/presentation\/blankstein."},{"key":"e_1_3_3_13_2","volume-title":"Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues","author":"Br\u00e9maud P.","year":"1998","unstructured":"P. Br\u00e9maud. 1998. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"e_1_3_3_15_2","first-page":"18","volume-title":"USENIX Symposium on Internet Technologies and Systems (USITS\u201997)","author":"Cao Pei","year":"1997","unstructured":"Pei Cao and Sandy Irani. 1997. Cost-aware WWW proxy caching algorithms. In USENIX Symposium on Internet Technologies and Systems (USITS\u201997). 18. http:\/\/portal.acm.org\/citation.cfm?id=1267297."},{"issue":"98","key":"e_1_3_3_16_2","article-title":"Improving WWW proxies performance with greedy-dual-size-frequency caching policy","author":"Cherkasova Ludmila","year":"1998","unstructured":"Ludmila Cherkasova. 1998. Improving WWW proxies performance with greedy-dual-size-frequency caching policy. HP Laboratories Technical Report98\u201369 (1998).","journal-title":"HP Laboratories Technical Report"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9502-9"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1972.tb00899.x"},{"key":"e_1_3_3_19_2","article-title":"An introduction to the theory of point processes: Elementary theory and methods","author":"Daley Daryl J.","year":"2003","unstructured":"Daryl J. Daley and David Vere-Jones. 2003. An introduction to the theory of point processes: Elementary theory and methods. Springer (2003).","journal-title":"Springer"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2004.11.001"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2014.34"},{"key":"e_1_3_3_22_2","first-page":"2263","volume-title":"IEEE INFOCOM 2015","author":"Garetto Michele","year":"2015","unstructured":"Michele Garetto, Emilio Leonardi, and Stefano Traverso. 2015. Efficient analysis of caching strategies under dynamic content popularity. In IEEE INFOCOM 2015. 2263\u20132271."},{"key":"e_1_3_3_23_2","volume-title":"Algorithm Design: Foundations, Analysis, and Internet Examples","author":"Goodrich Michael T.","year":"2002","unstructured":"Michael T. Goodrich and Roberto Tamassia. 2002. Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815675.2815677"},{"key":"e_1_3_3_25_2","volume-title":"37th Int. Symposium on Computer Architecture (ISCA\u201910)","author":"Jaleel Aamer","year":"2010","unstructured":"Aamer Jaleel, Kevin B. Theobald, Simon C. Steely, and Jr. Joel. 2010. High performance cache replacement using re-reference interval prediction (RRIP). In 37th Int. Symposium on Computer Architecture (ISCA\u201910). Saint Malo, France."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830400625X"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/511399.511340"},{"key":"e_1_3_3_28_2","volume-title":"Foundations of Modern Probability (2nd ed.)","author":"Kallenberg Olaf","year":"2001","unstructured":"Olaf Kallenberg. 2001. Foundations of Modern Probability (2nd ed.). Springer."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCC.2002.1021680"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1997.10473656"},{"key":"e_1_3_3_31_2","volume-title":"Multimedia Computing And Networking (MCNC\u201998)","author":"Liu Zhen","year":"1998","unstructured":"Zhen Liu, Philippe Nain, Nicolas Niclausse, and Don Towsley. 1998. Static caching of web servers. In Multimedia Computing And Networking (MCNC\u201998), SPIE Press (Ed.). San Jose, CA, USA."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2017.11.015"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/1090694.1090708"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-3267-7"},{"key":"e_1_3_3_35_2","volume-title":"Proc. of ITC-28","author":"Neglia Giovanni","year":"2016","unstructured":"Giovanni Neglia, Damiano Carra, Ming Dong Feng, Vaishnav Janardhan, Pietro Michiardi, and Dimitra Tsigkari. 2016. Access-time aware cache algorithms. In Proc. of ITC-28."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2017.2783623"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","unstructured":"Elizabeth J. O\u2019Neil Patrick E. O\u2019Neil and Gerhard Weikum. 1993. The LRU-K page replacement algorithm for database disk buffering. 22 2 (1993).","DOI":"10.1145\/170036.170081"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737446"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1983.10478000"},{"key":"e_1_3_3_40_2","article-title":"Analysis of Failure and Survival Data","author":"Smith P. J.","year":"2002","unstructured":"P. J. Smith. 2002. Analysis of Failure and Survival Data. Chapman and Hall (2002).","journal-title":"Chapman and Hall"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/516975"},{"issue":"3","key":"e_1_3_3_42_2","first-page":"989","article-title":"The estimation of the hazard function from randomly censored data by the kernel method","volume":"11","author":"Tanner Martin A.","year":"1983","unstructured":"Martin A. Tanner and Wing Hung Wong. 1983. The estimation of the hazard function from randomly censored data by the kernel method. The Annals of Statistics 11, 3 (1983), 989\u2013993.","journal-title":"The Annals of Statistics"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2541468.2541470"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2015.2458043"},{"key":"e_1_3_3_45_2","first-page":"4986","article-title":"Smoothing hazard rate","volume":"7","author":"Wang Jane-Ling","year":"2005","unstructured":"Jane-Ling Wang. 2005. Smoothing hazard rate. Encyclopedia of Biostatistics (2nd ed.) 7 (2005), 4986\u20134997.","journal-title":"Encyclopedia of Biostatistics"},{"issue":"136","key":"e_1_3_3_46_2","first-page":"1","article-title":"Platform and applications for massive-scale streaming network analytics","volume":"57","author":"Zerfos Petros","year":"2013","unstructured":"Petros Zerfos, Mudhakar Srivatsa, Hao Yu, David Dennerline, Hubertus Franke, and Dakshi Agrawal. 2013. Platform and applications for massive-scale streaming network analytics. IBM Journal for Research and Development: Special Edition on Massive Scale Analytics 57, 136 (2013), 1\u201311.","journal-title":"IBM Journal for Research and Development: Special Edition on Massive Scale Analytics"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3547332","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3547332","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3547332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:56Z","timestamp":1750186976000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3547332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,26]]},"references-count":45,"journal-issue":{"issue":"2-4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3547332"],"URL":"https:\/\/doi.org\/10.1145\/3547332","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"value":"2376-3639","type":"print"},{"value":"2376-3647","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,26]]},"assertion":[{"value":"2021-08-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}