{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:07:26Z","timestamp":1750306046342,"version":"3.41.0"},"publisher-location":"New York, New York, USA","reference-count":35,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1145\/3041021.3054187","type":"proceedings-article","created":{"date-parts":[[2018,1,11]],"date-time":"2018-01-11T18:39:25Z","timestamp":1515695965000},"page":"643-652","source":"Crossref","is-referenced-by-count":2,"title":["Caching with Dual Costs"],"prefix":"10.1145","author":[{"given":"Anirban","family":"Dasgupta","sequence":"first","affiliation":[{"name":"IIT Gandhinagar, Gandhinagar, India"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google, Mountain View, CA, USA"}]},{"given":"Tam\u00e1s","family":"Sarl\u00f3s","sequence":"additional","affiliation":[{"name":"Google, Mountain View, CA, USA"}]}],"member":"320","reference":[{"key":"key-10.1145\/3041021.3054187-1","doi-asserted-by":"crossref","unstructured":"A. Adamaszek, A. Czumaj, M. Englert, and H. Räcke. AnO(logk)-competitive algorithm for generalized caching. In SODA, 2012.","DOI":"10.1137\/1.9781611973099.133"},{"key":"key-10.1145\/3041021.3054187-2","doi-asserted-by":"crossref","unstructured":"S. Alici, I. S. Altingovde, R. Ozcan, B. B. Cambazoglu, and O. Ulusoy. Timestamp-based result cache invalidation for Web search engines. In SIGIR, pages 973--982, 2011.","DOI":"10.1145\/2009916.2010046"},{"key":"key-10.1145\/3041021.3054187-3","unstructured":"Y. Azar, U. Feige, and S. Nath. On the work function algorithm for two state task systems. Technical report, MSR-TR-2007--20, Microsoft, 2007."},{"key":"key-10.1145\/3041021.3054187-4","doi-asserted-by":"crossref","unstructured":"X. Bai and F. P. Junqueira. Online result cache invalidation for real-time Web search. In SIGIR, pages 641--650, 2012.","DOI":"10.1145\/2348283.2348369"},{"key":"key-10.1145\/3041021.3054187-5","doi-asserted-by":"crossref","unstructured":"N. Bansal, N. Buchbinder, and J. S. Naor. A primal-dual randomized algorithm for weighted paging. JACM, 59(4):19, 2012.","DOI":"10.1145\/2339123.2339126"},{"key":"key-10.1145\/3041021.3054187-6","doi-asserted-by":"crossref","unstructured":"W. Bein, L. Larmore, and J. Noga. Uniform metrical task systems with a limited number of states. IPL, 104(4):123--128, 2007.","DOI":"10.1016\/j.ipl.2007.06.001"},{"key":"key-10.1145\/3041021.3054187-7","doi-asserted-by":"crossref","unstructured":"L. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2):78--101, 1966.","DOI":"10.1147\/sj.52.0078"},{"key":"key-10.1145\/3041021.3054187-8","doi-asserted-by":"crossref","unstructured":"R. Blanco, E. Bortnikov, F. Junqueira, R. Lempel, L. Telloli, and H. Zaragoza. Caching search engine results over incremental indices. In WWW, pages 1065--1066, 2010.","DOI":"10.1145\/1772690.1772806"},{"key":"key-10.1145\/3041021.3054187-9","unstructured":"A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"key-10.1145\/3041021.3054187-10","doi-asserted-by":"crossref","unstructured":"N. Bruno and S. Chaudhuri. An online approach to physical design tuning. In ICDE, pages 826--835. IEEE, 2007.","DOI":"10.1109\/ICDE.2007.367928"},{"key":"key-10.1145\/3041021.3054187-11","doi-asserted-by":"crossref","unstructured":"B. B. Cambazoglu, F. P. Junqueira, V. Plachouras, S. Banachowski, B. Cui, and S. Lim. A refreshing perspective of search engine caching. In WWW, pages 181--190, 2010.","DOI":"10.1145\/1772690.1772710"},{"key":"key-10.1145\/3041021.3054187-12","doi-asserted-by":"crossref","unstructured":"B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. PVLDB, 1(2):1277--1288, 2008.","DOI":"10.14778\/1454159.1454167"},{"key":"key-10.1145\/3041021.3054187-13","doi-asserted-by":"crossref","unstructured":"A. Das, J. Gehrke, and M. Riedewald. Approximate join processing over data streams. In SIGMOD, pages 40--51, 2003.","DOI":"10.1145\/872757.872765"},{"key":"key-10.1145\/3041021.3054187-14","doi-asserted-by":"crossref","unstructured":"A. Fiat and M. Mendel. Better algorithms for unfair metrical task systems and applications. SICOMP, 32(6):1403--1422, 2003.","DOI":"10.1137\/S0097539700376159"},{"key":"key-10.1145\/3041021.3054187-15","doi-asserted-by":"crossref","unstructured":"G. Francès, X. Bai, B. Cambazoglu, and R. Baeza-Yates. Improving the efficiency of multi-site Web search engines. In WSDM, pages 3--12, 2014.","DOI":"10.1145\/2556195.2556249"},{"key":"key-10.1145\/3041021.3054187-16","doi-asserted-by":"crossref","unstructured":"K. Hose, D. Klan, and K.-U. Sattler. Online tuning of aggregation tables for olap. In ICDE, pages 1679--1686, 2009.","DOI":"10.1109\/ICDE.2009.155"},{"key":"key-10.1145\/3041021.3054187-17","doi-asserted-by":"crossref","unstructured":"Q. Huang, K. Birman, R. van Renesse, W. Lloyd, S. Kumar, and H. C. Li. An analysis of Facebook photo caching. In SOSP, pages 167--181, 2013.","DOI":"10.1145\/2517349.2522722"},{"key":"key-10.1145\/3041021.3054187-18","doi-asserted-by":"crossref","unstructured":"A. Karlin, M. Manasse, L. McGeoch, and S. Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica, 11(6):542--571, 1994.","DOI":"10.1007\/BF01189993"},{"key":"key-10.1145\/3041021.3054187-19","unstructured":"J. Kleinberg and E. Tardos. Algorithm Design. Pearson, 2005."},{"key":"key-10.1145\/3041021.3054187-20","doi-asserted-by":"crossref","unstructured":"I. Koltsidas and S. D. Viglas. Flashing up the storage layer. PVLDB, 1(1):514--525, 2008.","DOI":"10.14778\/1453856.1453913"},{"key":"key-10.1145\/3041021.3054187-21","doi-asserted-by":"crossref","unstructured":"R. Lempel and S. Moran. Predictive caching and prefetching of query results in search engines. In WWW, pages 19--28, 2003.","DOI":"10.1145\/775152.775156"},{"key":"key-10.1145\/3041021.3054187-22","doi-asserted-by":"crossref","unstructured":"R. Lempel and F. Silvestri. Web search result caching and prefetching. In Encyclopedia of Database Systems, pages 3501--3506. Springer, 2009.","DOI":"10.1007\/978-0-387-39940-9_464"},{"key":"key-10.1145\/3041021.3054187-23","doi-asserted-by":"crossref","unstructured":"X. Long and T. Suel. Three-level caching for efficient query processing in large Web search engines. In WWW, pages 257--266, 2005.","DOI":"10.1145\/1060745.1060785"},{"key":"key-10.1145\/3041021.3054187-24","doi-asserted-by":"crossref","unstructured":"H. Lu, K. Veeraraghavan, P. Ajoux, J. Hunt, Y. J. Song, W. Tobagus, S. Kumar, and W. Lloyd. Existential consistency: measuring and understanding consistency at Facebook. In SOSP, pages 295--310, 2015.","DOI":"10.1145\/2815400.2815426"},{"key":"key-10.1145\/3041021.3054187-25","doi-asserted-by":"crossref","unstructured":"T. Malik, X. Wang, R. Burns, D. Dash, and A. Ailamaki. Automated physical design in database caches. In ICDEW, pages 27--34, 2008.","DOI":"10.1109\/ICDEW.2008.4498281"},{"key":"key-10.1145\/3041021.3054187-26","doi-asserted-by":"crossref","unstructured":"S. Nath and A. Kansal. Flashdb: Dynamic self-tuning database for nand flash. In IPSN, pages 410--419, 2007.","DOI":"10.1109\/IPSN.2007.4379701"},{"key":"key-10.1145\/3041021.3054187-27","doi-asserted-by":"crossref","unstructured":"S. Pandey, A. Z. Broder, F. Chierichetti, V. Josifovski, R. Kumar, and S. Vassilvitskii. Nearest-neighbor caching for content-match applications. In WWW, pages 441--450, 2009.","DOI":"10.1145\/1526709.1526769"},{"key":"key-10.1145\/3041021.3054187-28","doi-asserted-by":"crossref","unstructured":"S. Paul and Z. Fei. Distributed caching with centralized control. Computer Communications, 24(2):256--268, 2001.","DOI":"10.1016\/S0140-3664(00)00322-4"},{"key":"key-10.1145\/3041021.3054187-29","unstructured":"M. Rabinovich and O. Spatscheck. Web Caching and Replication. Pearson, 2001."},{"key":"key-10.1145\/3041021.3054187-30","unstructured":"C. Ravishankar and J. Goodman. Cache implementation for multiple microprocessors. Computer Communications, pages 346--350, 1983."},{"key":"key-10.1145\/3041021.3054187-31","doi-asserted-by":"crossref","unstructured":"M. Satyanarayanan. A survey of distributed file systems. Annual Review of Computer Science, 4(1):73--104, 1990.","DOI":"10.1146\/annurev.cs.04.060190.000445"},{"key":"key-10.1145\/3041021.3054187-32","doi-asserted-by":"crossref","unstructured":"K. Schnaitter and N. Polyzotis. A benchmark for online index selection. In ICDE, pages 1701--1708, 2009.","DOI":"10.1109\/ICDE.2009.166"},{"key":"key-10.1145\/3041021.3054187-33","doi-asserted-by":"crossref","unstructured":"K. Schnaitter and N. Polyzotis. Semi-automatic index tuning: Keeping dbas in the loop. PVLDB, 5(5):478--489, 2012.","DOI":"10.14778\/2140436.2140444"},{"key":"key-10.1145\/3041021.3054187-34","doi-asserted-by":"crossref","unstructured":"J. Xie, J. Yang, and Y. Chen. On joining and caching stochastic streams. In SIGMOD, pages 359--370, 2005.","DOI":"10.1145\/1066157.1066199"},{"key":"key-10.1145\/3041021.3054187-35","doi-asserted-by":"crossref","unstructured":"J. Zhang, X. Long, and T. Suel. Performance of compressed inverted list caching in search engines. In WWW, pages 387--396, 2008.","DOI":"10.1145\/1367497.1367550"}],"event":{"number":"26","sponsor":["SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web","IW3C2, International World Wide Web Conference Committee"],"acronym":"WWW '17 Companion","name":"the 26th International Conference","start":{"date-parts":[[2017,4,3]]},"location":"Perth, Australia","end":{"date-parts":[[2017,4,7]]}},"container-title":["Proceedings of the 26th International Conference on World Wide Web Companion - WWW '17 Companion"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3041021.3054187","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3054187&ftid=1865175&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:03:19Z","timestamp":1750215799000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3041021.3054187"}},"subtitle":[],"proceedings-subject":"World Wide Web Companion","short-title":[],"issued":{"date-parts":[[2017]]},"references-count":35,"URL":"https:\/\/doi.org\/10.1145\/3041021.3054187","relation":{},"subject":[],"published":{"date-parts":[[2017]]}}}