{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:47Z","timestamp":1750220327031,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel Academy of Sciences and Humanities & Council for Higher Education","award":["Excellence Fellowship Program for International Postdoctoral Res"],"award-info":[{"award-number":["Excellence Fellowship Program for International Postdoctoral Res"]}]},{"name":"US-Israel BSF Grant","award":["2018352"],"award-info":[{"award-number":["2018352"]}]},{"name":"ISF grant","award":["2233\/19 (2027511)"],"award-info":[{"award-number":["2233\/19 (2027511)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538567","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"161-172","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Competitive Algorithms for Block-Aware Caching"],"prefix":"10.1145","author":[{"given":"Christian","family":"Coester","sequence":"first","affiliation":[{"name":"University of Sheffield, Sheffield, United Kingdom"}]},{"given":"Roie","family":"Levin","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Ohad","family":"Talmon","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00116-9"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3280826"},{"key":"e_1_3_2_1_3_1","volume-title":"Symposium on Discrete Algorithms. 31--40","author":"Albers Susanne","year":"1999","unstructured":"Susanne Albers , Sanjeev Arora , and Sanjeev Khanna . 1999 . Page replacement for general caching problems . In Symposium on Discrete Algorithms. 31--40 . Susanne Albers, Sanjeev Arora, and Sanjeev Khanna. 1999. Page replacement for general caching problems. In Symposium on Discrete Algorithms. 31--40."},{"volume-title":"Symposium on the Theory of Computation. 100--105","author":"Alon N.","key":"e_1_3_2_1_4_1","unstructured":"N. Alon , B. Awerbuch , Y. Azar , N. Buchbinder , and J. Naor . 2003. The online set cover problem . In Symposium on the Theory of Computation. 100--105 . N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. 2003. The online set cover problem. In Symposium on the Theory of Computation. 100--105."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339123.2339126"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779000"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461801"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.1"},{"key":"e_1_3_2_1_10_1","volume-title":"Brief Announcement: Block-Granularity-Aware Caching.","author":"Beckmann Nathan","year":"2021","unstructured":"Nathan Beckmann , Phillip B Gibbons , and Charles McGuffey . 2021 . Brief Announcement: Block-Granularity-Aware Caching. (2021). Nathan Beckmann, Phillip B Gibbons, and Charles McGuffey. 2021. Brief Announcement: Block-Granularity-Aware Caching. (2021)."},{"key":"e_1_3_2_1_11_1","volume-title":"Finely-Competitive Paging. In Symposium on Foundations of Computer Science (FOCS). 450","author":"Blum Avrim","year":"1999","unstructured":"Avrim Blum , Carl Burch , and Adam Kalai . 1999 . Finely-Competitive Paging. In Symposium on Foundations of Computer Science (FOCS). 450 . Avrim Blum, Carl Burch, and Adam Kalai. 1999. Finely-Competitive Paging. In Symposium on Foundations of Computer Science (FOCS). 450."},{"key":"e_1_3_2_1_12_1","unstructured":"A. Blum M. Furst and A. Tomkins. 1996. What to do with your free time: algorithms for infrequent requests and randomized weighted caching. (1996).  A. Blum M. Furst and A. Tomkins. 1996. What to do with your free time: algorithms for infrequent requests and randomized weighted caching. (1996)."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188798"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.32"},{"key":"e_1_3_2_1_15_1","volume-title":"Joseph Seffi Naor, et al","author":"Buchbinder Niv","year":"2009","unstructured":"Niv Buchbinder , Joseph Seffi Naor, et al . 2009 . The design of competitive online algorithms via a primal--dual approach. Foundations and Trends\u00ae in Theoretical Computer Science 3, 2--3 (2009), 93--263. Niv Buchbinder, Joseph Seffi Naor, et al. 2009. The design of competitive online algorithms via a primal--dual approach. Foundations and Trends\u00ae in Theoretical Computer Science 3, 2--3 (2009), 93--263."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Christian Coester Roie Levin Ohad Talmon etal 2022. Competitive Algorithms for Block-Aware Caching. arXiv preprint arXiv:2205.12249 (2022).  Christian Coester Roie Levin Ohad Talmon et al. 2022. Competitive Algorithms for Block-Aware Caching. arXiv preprint arXiv:2205.12249 (2022).","DOI":"10.1145\/3490148.3538567"},{"key":"e_1_3_2_1_18_1","volume-title":"Online Generalized Caching with Varying Weights and Costs. In Symposium on Parallelism in Algorithms and Architectures, SPAA. 205--212","author":"Even Guy","year":"2018","unstructured":"Guy Even , Moti Medina , and Dror Rawitz . 2018 . Online Generalized Caching with Varying Weights and Costs. In Symposium on Parallelism in Algorithms and Architectures, SPAA. 205--212 . Guy Even, Moti Medina, and Dror Rawitz. 2018. Online Generalized Caching with Varying Weights and Costs. In Symposium on Parallelism in Algorithms and Architectures, SPAA. 205--212."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"e_1_3_2_1_20_1","volume-title":"Elastic Caching. In Symposium on Discrete Algorithms, SODA. 143-- 156","author":"Gupta Anupam","year":"2019","unstructured":"Anupam Gupta , Ravishankar Krishnaswamy , Amit Kumar , and Debmalya Panigrahi . 2019 . Elastic Caching. In Symposium on Discrete Algorithms, SODA. 143-- 156 . Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. 2019. Elastic Caching. In Symposium on Discrete Algorithms, SODA. 143-- 156."},{"key":"e_1_3_2_1_21_1","volume-title":"Caching with Time Windows. In Symposium on Theory of Computing.","author":"Gupta Anupam","year":"2020","unstructured":"Anupam Gupta , Amit Kumar , and Debmalya Panigrahi . 2020 . Caching with Time Windows. In Symposium on Theory of Computing. Anupam Gupta, Amit Kumar, and Debmalya Panigrahi. 2020. Caching with Time Windows. In Symposium on Theory of Computing."},{"key":"e_1_3_2_1_22_1","volume-title":"Fully-Dynamic Submodular Cover with Bounded Recourse. In 2020 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE.","author":"Gupta Anupam","year":"2020","unstructured":"Anupam Gupta and Roie Levin . 2020 . Fully-Dynamic Submodular Cover with Bounded Recourse. In 2020 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. Anupam Gupta and Roie Levin. 2020. Fully-Dynamic Submodular Cover with Bounded Recourse. In 2020 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.94"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6847969"},{"key":"e_1_3_2_1_25_1","volume-title":"Proc. of the Dagstuhl Seminar on Online Algorithms.","author":"Irani Sandy","year":"1996","unstructured":"Sandy Irani . 1996 . Competitive analysis of paging: A survey . In Proc. of the Dagstuhl Seminar on Online Algorithms. Sandy Irani. 1996. Competitive analysis of paging: A survey. In Proc. of the Dagstuhl Seminar on Online Algorithms."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258666"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0095-6"},{"key":"e_1_3_2_1_28_1","volume-title":"Competitive Caching with Machine Learned Advice. In International Conference on Machine Learning, ICML","volume":"80","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvitskii . 2018 . Competitive Caching with Machine Learned Advice. In International Conference on Machine Learning, ICML , 2018, Vol. 80 . 3302--3311. Thodoris Lykouris and Sergei Vassilvitskii. 2018. Competitive Caching with Machine Learned Advice. In International Conference on Machine Learning, ICML, 2018, Vol. 80. 3302--3311."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_1_31_1","volume-title":"Learning Relaxed Belady for Content Distribution Network Caching. In 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020","author":"Song Zhenyu","year":"2020","unstructured":"Zhenyu Song , Daniel S. Berger , Kai Li , and Wyatt Lloyd . 2020 . Learning Relaxed Belady for Content Distribution Network Caching. In 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020 , Santa Clara, CA, USA, February 25--27 , 2020, Ranjita Bhagwan and George Porter (Eds.). USENIX Association, 529--544. Zhenyu Song, Daniel S. Berger, Kai Li, and Wyatt Lloyd. 2020. Learning Relaxed Belady for Content Distribution Network Caching. In 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020, Santa Clara, CA, USA, February 25--27, 2020, Ranjita Bhagwan and George Porter (Eds.). USENIX Association, 529--544."},{"key":"e_1_3_2_1_32_1","unstructured":"Jan Vondr\u00e1k. 2007. Submodularity in combinatorial optimization. (2007).  Jan Vondr\u00e1k. 2007. Submodularity in combinatorial optimization. (2007)."},{"key":"e_1_3_2_1_33_1","volume-title":"An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 4 (01","author":"Wolsey L. A.","year":"1982","unstructured":"L. A. Wolsey . 1982. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 4 (01 Dec 1982 ), 385--393. https:\/\/doi.org\/10. 1007\/BF02579435 L. A. Wolsey. 1982. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 4 (01 Dec 1982), 385--393. https:\/\/doi.org\/10. 1007\/BF02579435"},{"key":"e_1_3_2_1_34_1","volume-title":"Symposium on Discrete algorithms. 241--250","author":"Young Neal","year":"1991","unstructured":"Neal Young . 1991 . On-line caching as cache size varies . In Symposium on Discrete algorithms. 241--250 . Neal Young. 1991. On-line caching as cache size varies. In Symposium on Discrete algorithms. 241--250."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_3_2_1_36_1","volume-title":"Symposium on Discrete algorithms. 82--86","author":"Young Neal E.","year":"1998","unstructured":"Neal E. Young . 1998 . On-line file caching . In Symposium on Discrete algorithms. 82--86 . Neal E. Young. 1998. On-line file caching. In Symposium on Discrete algorithms. 82--86."}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","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"],"location":"Philadelphia PA USA","acronym":"SPAA '22"},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538567","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:08Z","timestamp":1750191128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":36,"alternative-id":["10.1145\/3490148.3538567","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538567","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}