{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T09:54:17Z","timestamp":1791021257307,"version":"4.1.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>Data-management-as-a-service systems are increasingly being used in collaborative settings, where multiple users access common datasets. Cloud providers have the choice to implement various optimizations, such as indexing or materialized views, to accelerate queries over these datasets. Each optimization carries a cost and may benefit multiple users. This creates a major challenge: how to select which optimizations to perform and how to share their cost among users. The problem is especially challenging when users are selfish and will only report their true values for different optimizations if doing so maximizes their utility.<\/jats:p>\n          <jats:p>In this paper, we present a new approach for selecting and pricing shared optimizations by using Mechanism Design. We first show how to apply the Shapley Value Mechanism to the simple case of selecting and pricing additive optimizations, assuming an offline game where all users access the service for the same time-period. Second, we extend the approach to online scenarios where users come and go. Finally, we consider the case of substitutive optimizations.<\/jats:p>\n          <jats:p>We show analytically that our mechanisms induce truthfulness and recover the optimization costs. We also show experimentally that our mechanisms yield higher utility than the state-of-the-art approach based on regret accumulation.<\/jats:p>","DOI":"10.14778\/2168651.2168657","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"562-573","source":"Crossref","is-referenced-by-count":27,"title":["How to price shared optimizations in the cloud"],"prefix":"10.14778","volume":"5","author":[{"given":"Prasang","family":"Upadhyaya","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Magdalena","family":"Balazinska","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-739X(02)00085-7"},{"key":"e_1_2_1_2_1","volume-title":"Free riding on gnutella","author":"Adar E.","year":"2000","unstructured":"E. Adar and B. A. Huberman . Free riding on gnutella , 2000 . E. Adar and B. A. Huberman. Free riding on gnutella, 2000."},{"key":"e_1_2_1_3_1","unstructured":"Amazon Web Services (AWS). aws.amazon.com.  Amazon Web Services (AWS). aws.amazon.com."},{"key":"e_1_2_1_4_1","unstructured":"Amazon Elastic MapReduce. aws.amazon.com\/elasticmapreduce.  Amazon Elastic MapReduce. aws.amazon.com\/elasticmapreduce."},{"key":"e_1_2_1_5_1","unstructured":"Amazon EC2 Instances. aws.amazon.com\/ec2\/instance-types\/.  Amazon EC2 Instances. aws.amazon.com\/ec2\/instance-types\/."},{"key":"e_1_2_1_6_1","unstructured":"Amazon Relational Database Service. aws.amazon.com\/rds\/.  Amazon Relational Database Service. aws.amazon.com\/rds\/."},{"key":"e_1_2_1_7_1","unstructured":"Amazon S3: Requester Pays Buckets. http:\/\/docs.amazonwebservices.com\/AmazonS3\/latest\/dev\/index.html?Reques%terPaysBuckets.html.  Amazon S3: Requester Pays Buckets. http:\/\/docs.amazonwebservices.com\/AmazonS3\/latest\/dev\/index.html?Reques%terPaysBuckets.html."},{"key":"e_1_2_1_8_1","unstructured":"Amazon Simple Storage Service (Amazon S3). http:\/\/www.amazon.com\/gp\/browse.html?node=16427261.  Amazon Simple Storage Service (Amazon S3). http:\/\/www.amazon.com\/gp\/browse.html?node=16427261."},{"key":"e_1_2_1_9_1","unstructured":"Amazon SimpleDB. http:\/\/www.amazon.com\/simpledb\/.  Amazon SimpleDB. http:\/\/www.amazon.com\/simpledb\/."},{"key":"e_1_2_1_10_1","unstructured":"Windows Azure Platform. microsoft.com\/windowsazure\/.  Windows Azure Platform. microsoft.com\/windowsazure\/."},{"key":"e_1_2_1_11_1","unstructured":"Windows Azure Storage Services REST API Ref. http:\/\/msdn.microsoft.com\/en-us\/library\/dd179355.aspx.  Windows Azure Storage Services REST API Ref. http:\/\/msdn.microsoft.com\/en-us\/library\/dd179355.aspx."},{"key":"e_1_2_1_12_1","first-page":"15","volume-title":"Proc. of the Symposium on Networked Systems Design and Implementation","author":"Balazinska M.","year":"2004","unstructured":"M. Balazinska , H. Balakrishnan , and M. Stonebraker . Contract-based load management in federated distributed systems . In Proc. of the Symposium on Networked Systems Design and Implementation , pages 15 -- 15 , 2004 . M. Balazinska, H. Balakrishnan, and M. Stonebraker. Contract-based load management in federated distributed systems. In Proc. of the Symposium on Networked Systems Design and Implementation, pages 15--15, 2004."},{"key":"e_1_2_1_13_1","volume-title":"Economic models for management of resources in peer-to-peer and grid computing","author":"Buyya R.","year":"2001","unstructured":"R. Buyya , H. Stockinger , J. Giddy , and D. Abramson . Economic models for management of resources in peer-to-peer and grid computing , 2001 . R. Buyya, H. Stockinger, J. Giddy, and D. Abramson. Economic models for management of resources in peer-to-peer and grid computing, 2001."},{"key":"e_1_2_1_15_1","volume-title":"Incentives build robustness in bittorrent","author":"Cohen B.","year":"2003","unstructured":"B. Cohen . Incentives build robustness in bittorrent , 2003 . B. Cohen. Incentives build robustness in bittorrent, 2003."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.143"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016527.1016539"},{"key":"e_1_2_1_18_1","first-page":"156","volume-title":"Economic models for allocating resources in computer systems","author":"Ferguson D. F.","year":"1996","unstructured":"D. F. Ferguson , C. Nikolaou , J. Sairamesh , and Y. Yemini . Economic models for allocating resources in computer systems , pages 156 -- 183 . World Scientific Publishing Co. , 1996 . D. F. Ferguson, C. Nikolaou, J. Sairamesh, and Y. Yemini. Economic models for allocating resources in computer systems, pages 156--183. World Scientific Publishing Co., 1996."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807158"},{"key":"e_1_2_1_20_1","unstructured":"Google App Engine. http:\/\/code.google.com\/appengine\/.  Google App Engine. http:\/\/code.google.com\/appengine\/."},{"key":"e_1_2_1_21_1","unstructured":"Google App Engine Datastore. code.google.com\/appengine\/docs\/datastore.  Google App Engine Datastore. code.google.com\/appengine\/docs\/datastore."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989358"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1876037.1876051"},{"key":"e_1_2_1_24_1","first-page":"5","volume-title":"HotCloud","author":"Li A.","year":"2010","unstructured":"A. Li , X. Yang , S. Kandula , and M. Zhang . CloudCmp: shopping for a cloud made easy . In HotCloud , pages 5 -- 5 , 2010 . A. Li, X. Yang, S. Kandula, and M. Zhang. CloudCmp: shopping for a cloud made easy. In HotCloud, pages 5--5, 2010."},{"key":"e_1_2_1_25_1","unstructured":"S. Loebman. Personal communication.  S. Loebman. Personal communication."},{"key":"e_1_2_1_26_1","unstructured":"Microsoft SQL Azure. microsoft.com\/windowsazure\/sqlazure\/.  Microsoft SQL Azure. microsoft.com\/windowsazure\/sqlazure\/."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00004200"},{"key":"e_1_2_1_28_1","unstructured":"About the Blue Waters project. ncsa.illinois.edu\/BlueWaters\/.  About the Blue Waters project. ncsa.illinois.edu\/BlueWaters\/."},{"key":"e_1_2_1_29_1","volume-title":"1st Workshop on the Economics of P2P systems","author":"Ng C.","year":"2003","unstructured":"C. Ng , D. C. Parkes , and M. Seltzer . Strategyproof computing: systems infrastructures for self-interested parties . In 1st Workshop on the Economics of P2P systems , 2003 . C. Ng, D. C. Parkes, and M. Seltzer. Strategyproof computing: systems infrastructures for self-interested parties. In 1st Workshop on the Economics of P2P systems, 2003."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45172-3_14"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1296179"},{"key":"e_1_2_1_32_1","first-page":"584","volume-title":"FOCS","author":"Pal M.","year":"2003","unstructured":"M. Pal and E. Tardos . Group strategyproof mechanisms via primal-dual algorithms . In FOCS , pages 584 -- 593 , 2003 . M. Pal and E. Tardos. Group strategyproof mechanisms via primal-dual algorithms. In FOCS, pages 584--593, 2003."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379350.1379360"},{"key":"e_1_2_1_35_1","unstructured":"Salesforce. http:\/\/www.salesforce.com\/.  Salesforce. http:\/\/www.salesforce.com\/."},{"key":"e_1_2_1_36_1","first-page":"295","volume-title":"Int'l Workshop on Distributed Artificial Intelligence","author":"Sandholm T.","year":"1993","unstructured":"T. Sandholm . An implementation of the contract net protocol based on marginal cost calculations . In Int'l Workshop on Distributed Artificial Intelligence , pages 295 -- 308 , 1993 . T. Sandholm. An implementation of the contract net protocol based on marginal cost calculations. In Int'l Workshop on Distributed Artificial Intelligence, pages 295--308, 1993."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03597"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050015"},{"key":"e_1_2_1_39_1","volume-title":"HotCloud","author":"Teregowda P. B.","year":"2010","unstructured":"P. B. Teregowda , B. Urgaonkar , and C. L. Giles . Implications of moving to the cloud: a digital libraries perspective . In HotCloud , 2010 . P. B. Teregowda, B. Urgaonkar, and C. L. Giles. Implications of moving to the cloud: a digital libraries perspective. In HotCloud, 2010."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767932"},{"key":"e_1_2_1_42_1","volume-title":"Workshop on the Economics of Peer-to-Peer Systems","author":"Vishnumurthy V.","year":"2003","unstructured":"V. Vishnumurthy , S. Chandrakumar , and E. G. Sirer . KARMA: A secure economic framework for peer-to-peer resource sharing . In Workshop on the Economics of Peer-to-Peer Systems , 2003 . V. Vishnumurthy, S. Chandrakumar, and E. G. Sirer. KARMA: A secure economic framework for peer-to-peer resource sharing. In Workshop on the Economics of Peer-to-Peer Systems, 2003."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.121753"},{"key":"e_1_2_1_44_1","first-page":"6","volume-title":"HotCloud","author":"Wang H.","year":"2010","unstructured":"H. Wang , Q. Jing , R. Chen , B. He , Z. Qian , and L. Zhou . Distributed systems meet economics: pricing in the cloud . In HotCloud , pages 6 -- 6 , 2010 . H. Wang, Q. Jing, R. Chen, B. He, Z. Qian, and L. Zhou. Distributed systems meet economics: pricing in the cloud. In HotCloud, pages 6--6, 2010."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2168651.2168657","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:18:18Z","timestamp":1672219098000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2168651.2168657"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.14778\/2168651.2168657"],"URL":"https:\/\/doi.org\/10.14778\/2168651.2168657","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,2]]}}}