{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T16:09:40Z","timestamp":1774541380049,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,17]],"date-time":"2023-06-17T00:00:00Z","timestamp":1686960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-2118830, CCF-2106827, CSR-1763680, CNS-1938709, CNS-2118620, CCF-2106999"],"award-info":[{"award-number":["CCF-2118830, CCF-2106827, CSR-1763680, CNS-1938709, CNS-2118620, CCF-2106999"]}]},{"name":"NSERC"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,17]]},"DOI":"10.1145\/3558481.3591084","type":"proceedings-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T22:22:03Z","timestamp":1685571723000},"page":"117-127","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["An Associativity Threshold Phenomenon in Set-Associative Caches"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-530X","authenticated-orcid":false,"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2416-6422","authenticated-orcid":false,"given":"Rathish","family":"Das","sequence":"additional","affiliation":[{"name":"University of Houston, Houston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8493-1395","authenticated-orcid":false,"given":"Guido","family":"Tagliavini","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3491003.3491013"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48012.48037"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400231"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.180"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538577"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9114-1"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2015.35"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1974.223948"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461814"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Michael A. Bender Rathish Das Mart\u00edn Farach-Colton and Guido Tagliavini. 2023. An Associativity Threshold Phenomenon in Set-Associative Caches. arxiv: 2304.04954 [cs.DS]","DOI":"10.1145\/3558481.3591084"},{"key":"e_1_3_2_1_12_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","unstructured":"Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press, USA."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSCC.2015.7062934"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-010-0123-6"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.001"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (Washington, D.C., USA). Society for Industrial and Applied Mathematics, USA, 374--383","author":"Brehob Mark","year":"2001","unstructured":"Mark Brehob, Richard Enbody, Eric Torng, and Stephen Wagner. 2001. On-Line Restricted Caching. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (Washington, D.C., USA). Society for Industrial and Applied Mathematics, USA, 374--383."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_18"},{"key":"e_1_3_2_1_18_1","volume-title":"Denning","author":"Coffman Edward G.","year":"1973","unstructured":"Edward G. Coffman and Peter J. Denning. 1973. Operating Systems Theory. Prentice Hall Professional Technical Reference."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400233"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538570"},{"key":"e_1_3_2_1_21_1","volume-title":"Closing the Gap Between Theory and Practice: New Measures for On-line Algorithm Analysis. In International Workshop on Algorithms and Computation (WALCOM). Springer-Verlag Berlin Heidelberg, 13--24","author":"Dorrigiv Reza","year":"2008","unstructured":"Reza Dorrigiv and Alejandro L\u00f3pez-Ortiz. 2008. Closing the Gap Between Theory and Practice: New Measures for On-line Algorithm Analysis. In International Workshop on Algorithms and Computation (WALCOM). Springer-Verlag Berlin Heidelberg, 13--24."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.04.023"},{"key":"e_1_3_2_1_23_1","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"Dubhashi Devdatt","unstructured":"Devdatt Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms 1st ed.). Cambridge University Press, USA.","edition":"1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644203"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.805152"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.16187"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.40842"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/325096.325162"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.14"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.1989.714547"},{"key":"e_1_3_2_1_33_1","volume-title":"Analysis of Demand Paging Algorithms. In IFIP Congress.","author":"King William F.","year":"1971","unstructured":"William F. King. 1971. Analysis of Demand Paging Algorithms. In IFIP Congress."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.2015.2456902"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSCC.2014.6757361"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.015"},{"key":"e_1_3_2_1_38_1","unstructured":"Nima Mousavi. 2012. How tight is Chernoff bound? Notes."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170081"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300518"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644202"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the 15th Annual International Symposium on Computer Architecture (ISCA)","author":"Prybylski S.","unstructured":"S. Prybylski, M. Horowitz, and J. Hennessy. 1988. Performance Tradeoffs in Cache Design. In Proceedings of the 15th Annual International Symposium on Computer Architecture (ISCA) (Honolulu, Hawaii, USA). IEEE Computer Society, Washington, DC, USA, 290--298."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2018.00068"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322246"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322081"},{"key":"e_1_3_2_1_46_1","unstructured":"RocksDB. 2022. Block Cache. RocksDB wiki. https:\/\/github.com\/facebook\/rocksdb\/wiki\/Block-Cache Last accessed: 2023-01-09."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2022.3164338"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/646229.681726"},{"key":"e_1_3_2_1_49_1","volume-title":"Proceedings of the International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS). Association for Computing Machinery","author":"Sen Rathijit","unstructured":"Rathijit Sen and David A. Wood. 2013. Reuse-Based Online Models for Caches. In Proceedings of the International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS). Association for Computing Machinery, New York, NY, USA, 279--292."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602225"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/800253.807689"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1978.231482"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSCC.2018.8310170"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.752660"},{"key":"e_1_3_2_1_56_1","unstructured":"David Wajc. 2017. Negative Association - Definition Properties and Applications."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451153"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0124-5"}],"event":{"name":"SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Orlando FL USA","acronym":"SPAA '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591084","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591084","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:06Z","timestamp":1750178826000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,17]]},"references-count":59,"alternative-id":["10.1145\/3558481.3591084","10.1145\/3558481"],"URL":"https:\/\/doi.org\/10.1145\/3558481.3591084","relation":{},"subject":[],"published":{"date-parts":[[2023,6,17]]},"assertion":[{"value":"2023-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}