{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T12:37:37Z","timestamp":1762087057023,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031312335"},{"type":"electronic","value":"9783031312342"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-31234-2_9","type":"book-chapter","created":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T09:02:40Z","timestamp":1683018160000},"page":"147-163","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Regret-Optimal Online Caching for\u00a0Adversarial and\u00a0Stochastic Arrivals"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5663-8308","authenticated-orcid":false,"given":"Fathima Zarin","family":"Faizal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1658-1116","authenticated-orcid":false,"given":"Priya","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7233-0717","authenticated-orcid":false,"given":"Nikhil","family":"Karamchandani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9393-9276","authenticated-orcid":false,"given":"Sharayu","family":"Moharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,3]]},"reference":[{"unstructured":"https:\/\/github.com\/fathimazarin\/Valuetools2022_caching\/blob\/main\/main.pdf","key":"9_CR1"},{"unstructured":"MovieLens 1M dataset. https:\/\/grouplens.org\/datasets\/movielens\/. Accessed 8 Aug 2022","key":"9_CR2"},{"doi-asserted-by":"publisher","unstructured":"Aggarwal, C., Wolf, J.L., Yu, P.S.: Caching on the world wide web. 125 J. Distrib. Parallel Syst. (IJDPS) 2(6), 94\u2013107 (2000). https:\/\/doi.org\/10.1109\/69.755618","key":"9_CR3","DOI":"10.1109\/69.755618"},{"key":"9_CR4","volume-title":"Competitive Online Algorithms","author":"S Albers","year":"1996","unstructured":"Albers, S.: Competitive Online Algorithms. BRICS, Shanghai (1996)"},{"doi-asserted-by":"publisher","unstructured":"Alon, N., Spencer, J.: Appendix B: Paul Erd\u00f6s. John Wiley and Sons, Ltd, New York (2008). https:\/\/doi.org\/10.1002\/9780470277331.app2","key":"9_CR5","DOI":"10.1002\/9780470277331.app2"},{"key":"9_CR6","volume-title":"Stochastic Analysis of Computer Storage","author":"OI Aven","year":"1987","unstructured":"Aven, O.I., Coffman, E.G., Kogan, Y.A.: Stochastic Analysis of Computer Storage. Kluwer Academic Publishers, USA (1987)"},{"doi-asserted-by":"publisher","unstructured":"Bhattacharjee, R., Banerjee, S., Sinha, A.: Fundamental limits of online network-caching. CoRR abs\/2003.14085 (2020). https:\/\/doi.org\/10.48550\/arXiv.2003.14085","key":"9_CR7","DOI":"10.48550\/arXiv.2003.14085"},{"doi-asserted-by":"publisher","unstructured":"Bura, A., Rengarajan, D., Kalathil, D., Shakkottai, S., Chamberland, J.F.: Learning to cache and caching to learn: regret analysis of caching algorithms. IEEE\/ACM Trans. Netw. 30(1), 18\u201331 (2022). https:\/\/doi.org\/10.48550\/arXiv.2004.00472","key":"9_CR8","DOI":"10.48550\/arXiv.2004.00472"},{"doi-asserted-by":"publisher","unstructured":"Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, Cambridge (2006). https:\/\/doi.org\/10.1017\/CBO9780511546921","key":"9_CR9","DOI":"10.1017\/CBO9780511546921"},{"unstructured":"Cohen, A., Hazan, T.: Following the perturbed leader for online structured learning. In: Bach, F., Blei, D. (eds.) Proceedings of the 32nd International Conference on Machine Learning. Proceedings of Machine Learning Research, PMLR, Lille, France, vol. 37, pp. 1034\u20131042, 07\u201309 July 2015","key":"9_CR10"},{"doi-asserted-by":"publisher","unstructured":"Hannan, J.: Approximation to Bayes risk in repeated play. In: Contributions to the Theory of Games, vol. 3, no. 2, 97\u2013139 (1957). https:\/\/doi.org\/10.1515\/9781400882151","key":"9_CR11","DOI":"10.1515\/9781400882151"},{"doi-asserted-by":"publisher","unstructured":"Harper, F.M., Konstan, J.A.: The Movielens datasets: history and context. ACM Trans. Interact. Intell. Syst. 5(4), December 2015. https:\/\/doi.org\/10.1145\/2827872","key":"9_CR12","DOI":"10.1145\/2827872"},{"issue":"301","key":"9_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963). https:\/\/doi.org\/10.1080\/01621459.1963.10500830","journal-title":"J. Am. Stat. Assoc."},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1111\/j.1467-9574.1980.tb00681.x","volume":"34","author":"R Kaas","year":"1980","unstructured":"Kaas, R., Buhrman, J.M.: Mean, median and mode in binomial distributions. Stat. Neerl. 34(1), 13\u201318 (1980). https:\/\/doi.org\/10.1111\/j.1467-9574.1980.tb00681.x","journal-title":"Stat. Neerl."},{"doi-asserted-by":"publisher","unstructured":"Lattimore, T., Szepesv\u00e1ri, C.: Bandit Algorithms. Cambridge University Press, Cambridge (2020). https:\/\/doi.org\/10.1017\/9781108571401","key":"9_CR15","DOI":"10.1017\/9781108571401"},{"issue":"2","key":"9_CR16","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1006\/inco.1994.1009","volume":"108","author":"N Littlestone","year":"1994","unstructured":"Littlestone, N., Warmuth, M.K.: The weighted majority algorithm. Inf. Comput. 108(2), 212\u2013261 (1994). https:\/\/doi.org\/10.1006\/inco.1994.1009","journal-title":"Inf. Comput."},{"doi-asserted-by":"publisher","unstructured":"Mourtada, J., Ga\u00efffas, S.: On the optimality of the hedge algorithm in the stochastic regime. J. Mach. Learn. Res. 20, 1\u201328 (2019). https:\/\/doi.org\/10.48550\/arXiv.1809.01382","key":"9_CR17","DOI":"10.48550\/arXiv.1809.01382"},{"doi-asserted-by":"publisher","unstructured":"Mukhopadhyay, S., Sinha, A.: Online caching with optimal switching regret. CoRR abs\/2101.07043 (2021). https:\/\/doi.org\/10.1109\/ISIT45174.2021.9517925","key":"9_CR18","DOI":"10.1109\/ISIT45174.2021.9517925"},{"doi-asserted-by":"publisher","unstructured":"Paria, D., Sinha, A.: Leadcache: regret-optimal caching in networks. In: Thirty-Fifth Conference on Neural Information Processing Systems, vol. 34, pp. 4435\u20134447 (2021). https:\/\/doi.org\/10.48550\/arXiv.2009.08228","key":"9_CR19","DOI":"10.48550\/arXiv.2009.08228"},{"doi-asserted-by":"publisher","unstructured":"Paschos, G.S., Destounis, A., Vigneri, L., Iosifidis, G.: Learning to cache with no regrets. In: IEEE INFOCOM 2019 - IEEE Conference on Computer Communications, pp. 235\u2013243. IEEE Press (2019). https:\/\/doi.org\/10.1109\/INFOCOM.2019.8737446","key":"9_CR20","DOI":"10.1109\/INFOCOM.2019.8737446"},{"key":"9_CR21","volume-title":"Operating System Principles","author":"A Silberschatz","year":"2006","unstructured":"Silberschatz, A., Galvin, P., Gagne, G.: Operating System Principles. John Wiley & Sons, Hoboken (2006)"},{"doi-asserted-by":"publisher","unstructured":"Starobinski, D., Tse, D.: Probabilistic methods for web caching. Perform. Eval. 46(2\u20133), 125\u2013137, October 2001. https:\/\/doi.org\/10.1016\/S0166-5316(01)00045-1","key":"9_CR22","DOI":"10.1016\/S0166-5316(01)00045-1"},{"unstructured":"Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 928\u2013936 (2003)","key":"9_CR23"}],"container-title":["Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering","Performance Evaluation Methodologies and Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-31234-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T09:17:30Z","timestamp":1683019050000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-31234-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031312335","9783031312342"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-31234-2_9","relation":{},"ISSN":["1867-8211","1867-822X"],"issn-type":[{"type":"print","value":"1867-8211"},{"type":"electronic","value":"1867-822X"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"3 May 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"VALUETOOLS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"EAI International Conference on Performance Evaluation Methodologies and Tools","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"valuetools2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Confy+","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"18","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}