{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:40:09Z","timestamp":1755790809387,"version":"3.44.0"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Cloud object stores offer vastly different price points for object storage as a function of workload and geography. Poor object placement can thus lead to significant cost overheads. Prior cost-saving techniques attempt to optimize placement policies on the fly, deciding object placements for each object individually. In practice, these techniques do not scale to the size of the modern cloud. In this work, we leverage the static nature and pay-per-use pricing model of cloud environments to explore a different approach. Rather than computing object placements on the fly, we precompute a SkyPIE oracle---a lookup structure representing all possible placement policies and the workloads for which they are optimal. Internally, SkyPIE represents placement policies as a matrix of cost-hyperplanes, which we effectively precompute through pruning and convex optimization. By leveraging a fast geometric algorithm, online queries then are 1 to 8 orders of magnitude faster but as accurate as Integer-Linear-Programming. This makes exact optimization tractable for real workloads and we show &gt;10x cost savings compared to state-of-the-art heuristic approaches.<\/jats:p>","DOI":"10.1145\/3639310","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["SkyPIE: A Fast &amp; Accurate Oracle for Object Placement"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0826-8645","authenticated-orcid":false,"given":"Tiemo","family":"Bang","sequence":"first","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2628-354X","authenticated-orcid":false,"given":"Chris","family":"Douglas","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3567-801X","authenticated-orcid":false,"given":"Natacha","family":"Crooks","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7712-4306","authenticated-orcid":false,"given":"Joseph M.","family":"Hellerstein","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00144--1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807165"},{"key":"e_1_2_1_3_1","volume-title":"Volley: Automated data placement for geo-distributed cloud services","author":"Agarwal Sharad","year":"2010","unstructured":"Sharad Agarwal, John Dunagan, Navendu Jain, Stefan Saroiu, Alec Wolman, and Habinder Bhogan. 2010. Volley: Automated data placement for geo-distributed cloud services. In NSDI. USENIX Association, USA, 2."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2017.7996728"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/502912.502915"},{"key":"e_1_2_1_6_1","unstructured":"Amazon Web Services. 2023. Slack Case Study. https:\/\/aws.amazon.com\/solutions\/case-studies\/slack\/"},{"key":"e_1_2_1_7_1","volume-title":"Conference on File and Storage Technologies (FAST 02)","author":"Anderson Eric","year":"2002","unstructured":"Eric Anderson, Michael Hobbs, Kimberly Keeton, Susan Spence, Mustafa Uysal, and Alistair Veitch. 2002. Hippodrome: running circles around storage administration. In Conference on File and Storage Technologies (FAST 02). USENIX Association, USA, 13."},{"key":"e_1_2_1_8_1","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Annamalai Muthukaruppan","year":"2018","unstructured":"Muthukaruppan Annamalai, Kaushik Ravichandran, Harish Srinivas, Igor Zinkovsky, Luning Pan, Tony Savor, David Nagle, and Michael Stumm. 2018. Sharding the Shards: Managing Datastore Locality at Scale with Akkio. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). USENIX Association, Carlsbad, CA, 445--460. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/annamalai"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"Mosek optimization toolbox for matlab. User's Guide and Reference Manual","volume":"4","author":"Mosek","year":"2019","unstructured":"Mosek ApS. 2019. Mosek optimization toolbox for matlab. User's Guide and Reference Manual, Version, Vol. 4 (2019), 1.","journal-title":"Version"},{"key":"e_1_2_1_10_1","unstructured":"Mosek ApS. 2023. Advanced hot-start. https:\/\/docs.mosek.com\/10.0\/toolbox\/advanced-hotstart.html"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2685048.2685077"},{"key":"e_1_2_1_12_1","unstructured":"Microsoft Azure. 2023 a. Azure Blob Storage. https:\/\/azure.microsoft.com\/en-us\/products\/storage\/blobs\/"},{"key":"e_1_2_1_13_1","unstructured":"Microsoft Azure. 2023 b. Estimate the cost of archiving data. https:\/\/learn.microsoft.com\/en-us\/azure\/storage\/blobs\/archive-cost-estimation#the-cost-to-rehydrate"},{"key":"e_1_2_1_14_1","unstructured":"Microsoft Azure. 2023 c. Object replication for block blobs. https:\/\/learn.microsoft.com\/en-us\/azure\/storage\/blobs\/object-replication-overview"},{"key":"e_1_2_1_15_1","unstructured":"Microsoft Azure. 2023 d. Optimize costs for Blob storage with reserved capacity. https:\/\/learn.microsoft.com\/en-us\/azure\/storage\/blobs\/storage-blob-reserved-capacity"},{"key":"e_1_2_1_16_1","unstructured":"Microsoft Azure. 2023 e. Pricing API. https:\/\/learn.microsoft.com\/en-us\/rest\/api\/cost-management\/retail-prices\/azure-retail-prices"},{"key":"e_1_2_1_17_1","unstructured":"Microsoft Azure. 2023 f. Pricing Calculator. https:\/\/azure.microsoft.com\/en-us\/pricing\/calculator\/"},{"key":"e_1_2_1_18_1","volume-title":"Hellerstein","author":"Bang Tiemo","year":"2023","unstructured":"Tiemo Bang, Chris Dougals, Natacha Crooks, and Joeseph M. Hellerstein. 2023. Cloud Oracle\/SkyPIE Github Repo. https:\/\/github.com\/hydro-project\/cloud_oracle"},{"key":"e_1_2_1_19_1","volume-title":"14th Annual Conference on Innovative Data Systems Research, CIDR 2024 Chaminade, USA, January 14--17, 2024","author":"Bang Tiemo","year":"2024","unstructured":"Tiemo Bang, Conor Power, Siavash Ameli, Natacha Crooks, and Joseph M. Hellerstein. 2024. Optimizing the cloud? Don't train models. Build oracles!. In 14th Annual Conference on Innovative Data Systems Research, CIDR 2024 Chaminade, USA, January 14--17, 2024. www.cidrdb.org. https:\/\/www.cidrdb.org\/cidr2024\/papers\/p47-bang.pdf"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574260"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234200"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00276"},{"key":"e_1_2_1_24_1","unstructured":"Sebastien Bubeck. 2011. Introduction to Online Optimization. http:\/\/sbubeck.com\/BubeckLectureNotes.pdf"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3412841.3441886"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365723"},{"key":"e_1_2_1_27_1","unstructured":"Google Cloud. 2023. Cloud Storage. https:\/\/cloud.google.com\/storage\/"},{"key":"e_1_2_1_28_1","unstructured":"CloudFlare. 2023. Pricing CloudFlare R2 Docs. https:\/\/developers.cloudflare.com\/r2\/pricing\/"},{"key":"e_1_2_1_29_1","unstructured":"IBM Corporation. 2022. Starting from a solution: MIP starts. https:\/\/www.ibm.com\/docs\/en\/icos\/22.1.0?topic=mip-starting-from-solution-starts"},{"key":"e_1_2_1_30_1","unstructured":"NVIDIA Corporation. 2023 a. NVIDIA DGX-1. https:\/\/images.nvidia.com\/content\/pdf\/dgx1-v100-system-architecture-whitepaper.pdf"},{"key":"e_1_2_1_31_1","unstructured":"NVIDIA Corporation. 2023 b. NVIDIA Tesla V100 GPU Architecture. https:\/\/images.nvidia.com\/content\/volta-architecture\/pdf\/volta-architecture-whitepaper.pdf"},{"key":"e_1_2_1_32_1","unstructured":"Oracle Corporation. 2023 c. Object Storage. https:\/\/www.oracle.com\/cloud\/storage\/object-storage\/"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611486"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/800250.807481"},{"key":"e_1_2_1_35_1","volume-title":"Spring","author":"Fukuda Komei","year":"2015","unstructured":"Komei Fukuda. 2015. Lecture - Polyhedral Computation, Spring 2015. https:\/\/people.inf.ethz.ch\/fukudak\/lect\/pclect\/notes2015\/PolyComp2015.pdf"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20086-6_14"},{"key":"e_1_2_1_37_1","unstructured":"Greg Glockner. 2023. Does Gurobi support GPUs? https:\/\/support.gurobi.com\/hc\/en-us\/articles\/360012237852-Does-Gurobi-support-GPUs"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815675.2815677"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.42"},{"volume-title":"Dual methods in mixed integer linear programming. Ph.,D. Dissertation","author":"Guzelsoy Menal","key":"e_1_2_1_41_1","unstructured":"Menal Guzelsoy. 2009. Dual methods in mixed integer linear programming. Ph.,D. Dissertation. Lehigh University PhD."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10080"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263688"},{"key":"e_1_2_1_44_1","unstructured":"Backblaze Inc. 2023 a. B2 Cloud Storage. https:\/\/www.backblaze.com\/b2\/cloud-storage.html"},{"key":"e_1_2_1_45_1","unstructured":"Cloudflare Inc. 2023 b. Cloudflare R2. https:\/\/www.cloudflare.com\/products\/r2\/"},{"key":"e_1_2_1_46_1","volume-title":"Skyplane: Optimizing Transfer Cost and Throughput Using Cloud-Aware Overlays","author":"Jain Paras","year":"2023","unstructured":"Paras Jain, Sam Kumar, Sarah Wooders, Shishir G. Patil, Joseph E. Gonzalez, and Ion Stoica. 2023. Skyplane: Optimizing Transfer Cost and Throughput Using Cloud-Aware Overlays. USENIX Association, USA, 1375--1389. https:\/\/www.usenix.org\/conference\/nsdi23\/presentation\/jain"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402740"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_49_1","volume-title":"USENIX Annual Technical Conference. USENIX Association, USA, 129--142","author":"Kotla Ramakrishna","year":"2007","unstructured":"Ramakrishna Kotla, Lorenzo Alvisi, and Mike Dahlin. 2007. SafeStore: A durable and practical storage system. In USENIX Annual Technical Conference. USENIX Association, USA, 129--142."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.01.007"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.2968321"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.23919\/WiOpt56218.2022.9930570"},{"key":"e_1_2_1_53_1","volume-title":"Scc: Cluster storage provisioning informed by application characteristics and SLAs.","author":"Madhyastha Harsha V","year":"2012","unstructured":"Harsha V Madhyastha, John McCullough, George Porter, Rishi Kapoor, Stefan Savage, Alex C Snoeren, and Amin Vahdat. 2012. Scc: Cluster storage provisioning informed by application characteristics and SLAs.. In FAST. USENIX Association, USA, 23."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2017.2659728"},{"key":"e_1_2_1_55_1","unstructured":"Paul Miller Pascal Matzke Will McKeon-White Christopher Voce and Ian McPherson. 2018. A Clear Multicloud Strategy Delivers Business Value. https:\/\/www.forrester.com\/report\/a-clear-multicloud-strategy-delivers-business-value\/RES128781"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078468.3078485"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380609"},{"key":"e_1_2_1_58_1","unstructured":"Google Cloud Platform. 2023 a. Cloud Storage Always Free usage limits. https:\/\/cloud.google.com\/storage\/pricing#cloud-storage-always-free"},{"key":"e_1_2_1_59_1","unstructured":"Google Cloud Platform. 2023 b. Data Availability and Durability. https:\/\/cloud.google.com\/storage\/docs\/availability-durability#cross-region-redundancy"},{"key":"e_1_2_1_60_1","unstructured":"Google Cloud Platform. 2023 c. Pricing Calculator. https:\/\/cloud.google.com\/products\/calculator"},{"key":"e_1_2_1_61_1","unstructured":"Ted Ralphs. 2006. Duality and Warm Starting in Integer Programming. https:\/\/coral.ise.lehigh.edu\/ ted\/files\/papers\/DMII06.pdf"},{"key":"e_1_2_1_62_1","volume-title":"Model predictive control: theory, computation, and design","author":"Rawlings James Blake","unstructured":"James Blake Rawlings, David Q. Mayne, and Moritz Diehl. 2017. Model predictive control: theory, computation, and design 2nd edition ed.). Nob Hill Publishing, Madison, Wisconsin.","edition":"2"},{"key":"e_1_2_1_63_1","unstructured":"Timos Sellis Nick Roussopoulos and Christos Faloutsos. 1987. The R-Tree: A Dynamic Index for Multi-Dimensional Objects. Technical Report. University of Maryland."},{"key":"e_1_2_1_64_1","unstructured":"Amazon Web Services. 2023 a. Amazon S3 Intelligent-Tiering storage class. https:\/\/aws.amazon.com\/s3\/storage-classes\/intelligent-tiering\/"},{"key":"e_1_2_1_65_1","unstructured":"Amazon Web Services. 2023 b. Amazon S3 Replication. https:\/\/aws.amazon.com\/s3\/features\/replication\/"},{"key":"e_1_2_1_66_1","unstructured":"Amazon Web Services. 2023 c. Cloud Object Storage. https:\/\/aws.amazon.com\/s3\/"},{"key":"e_1_2_1_67_1","unstructured":"Amazon Web Services. 2023 d. Performance Design Patterns for Amazon S3. https:\/\/docs.aws.amazon.com\/AmazonS3\/latest\/userguide\/optimizing-performance-design-patterns.html"},{"key":"e_1_2_1_68_1","unstructured":"Amazon Web Services. 2023 e. Pricing API. https:\/\/pricing.us-east-1.amazonaws.com\/offers\/v1.0\/aws\/index.json"},{"key":"e_1_2_1_69_1","unstructured":"Amazon Web Services. 2023 f. Pricing Calculator. https:\/\/calculator.aws\/"},{"key":"e_1_2_1_70_1","unstructured":"Amazon Web Services. 2023 g. Restoring an archived object. https:\/\/docs.aws.amazon.com\/AmazonS3\/latest\/userguide\/restoring-objects.html"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2014.34"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824047"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352133"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522731"},{"key":"e_1_2_1_75_1","volume-title":"Faust: A Tragedy, in Two Parts","author":"Von Goethe Johann Wolfgang","year":"1843","unstructured":"Johann Wolfgang Von Goethe. 1843. Faust: A Tragedy, in Two Parts. Chapman and Hall."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS51616.2021.00023"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC45484.2021.9682955"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522730"},{"key":"e_1_2_1_79_1","volume-title":"Gautam Mittal, Scott Shenker, and Ion Stoica.","author":"Yang Zongheng","year":"2023","unstructured":"Zongheng Yang, Zhanghao Wu, Michael Luo, Wei-Lin Chiang, Romil Bhardwaj, Woosuk Kwon, Siyuan Zhuang, Frank Sifei Luan, Gautam Mittal, Scott Shenker, and Ion Stoica. 2023. SkyPilot: An Intercloud Broker for Sky Computing. USENIX Association, USA, 437--455. https:\/\/www.usenix.org\/conference\/nsdi23\/presentation\/yang-zongheng"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547323"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639310","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639310","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:14:31Z","timestamp":1755789271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639310"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":80,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639310"],"URL":"https:\/\/doi.org\/10.1145\/3639310","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}