{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:14Z","timestamp":1750306094649,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,5,26]],"date-time":"2017-05-26T00:00:00Z","timestamp":1495756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006234","name":"Sandia National Laboratories","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006234","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS 1247726, CCF 1217708, CCF 1114809, CCF 0937822, CCF 1617618, IIS 1247750, CCF 1114930 and CCF 1218188"],"award-info":[{"award-number":["IIS 1247726, CCF 1217708, CCF 1114809, CCF 0937822, CCF 1617618, IIS 1247750, CCF 1114930 and CCF 1218188"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Research Group FOR 1800"},{"name":"MOE Tier 2","award":["MOE2014-T2-1-157"],"award-info":[{"award-number":["MOE2014-T2-1-157"]}]},{"name":"DFG","award":["FE407\/17-1 and 17-2"],"award-info":[{"award-number":["FE407\/17-1 and 17-2"]}]},{"name":"Controlling Concurrent Change"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>\n            Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the\n            <jats:bold>\n              <jats:italic>memory allocation<\/jats:italic>\n            <\/jats:bold>\n            problem. The competitive ratio for this problem has matching upper and lower bounds that are logarithmic in the number of requests and in the ratio of the largest to smallest requests.\n          <\/jats:p>\n          <jats:p>\n            This article defines the\n            <jats:bold>\n              <jats:italic>storage reallocation<\/jats:italic>\n            <\/jats:bold>\n            problem, where previously allocated blocks can be moved, or\n            <jats:bold>\n              <jats:italic>reallocated<\/jats:italic>\n            <\/jats:bold>\n            , but at some cost. This cost is determined by the allocation\/reallocation\n            <jats:bold>\n              <jats:italic>cost function<\/jats:italic>\n            <\/jats:bold>\n            .\n          <\/jats:p>\n          <jats:p>\n            The objective is to minimize the storage footprint, that is, the largest memory address containing an allocated object, while simultaneously minimizing the reallocation costs. This article gives asymptotically optimal algorithms for storage reallocation, in which the storage footprint is at most (1+ \u03f5) times optimal, and the reallocation cost is\n            <jats:italic>O<\/jats:italic>\n            ((1\/\u03f5)log (1\/\u03f5)) times the original allocation cost, that is, it is within a constant factor of optimal when \u03f5 is a constant. The algorithms are\n            <jats:bold>\n              <jats:italic>cost oblivious<\/jats:italic>\n            <\/jats:bold>\n            , which means they achieve these bounds with no knowledge of the allocation\/reallocation cost function, as long as the cost function is subadditive.\n          <\/jats:p>","DOI":"10.1145\/3070693","type":"journal-article","created":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T19:32:40Z","timestamp":1496259160000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Cost-Oblivious Storage Reallocation"],"prefix":"10.1145","volume":"13","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, NY, USA"}]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":false,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"additional","affiliation":[{"name":"TU Braunschweig, Braunschweig, Germany"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[{"name":"Georgetown University, DC, USA"}]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2017,5,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28428"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10091"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.08.003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1142\/9781848162778_0004"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.12.001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902276"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740801"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935798"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389956"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634145"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486181"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594548"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1237-z"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789494.1789499"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039784"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142355"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292616"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755589"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2362389.2362392"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90046-0"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-34735-6_21"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214083"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212014"},{"key":"e_1_2_1_24_1","unstructured":"Edward G. Coffman Jr. M. R. Garey and D. S. Johnson. 1997. Approximation Algorithms for NP-hard Problems. PWS Publishing Co. Chapter Approximation Algorithms for Bin Packing: A Survey 46--93.   Edward G. Coffman Jr. M. R. Garey and D. S. Johnson. 1997. Approximation Algorithms for NP-hard Problems. PWS Publishing Co. Chapter Approximation Algorithms for Bin Packing: A Survey 46--93."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167203"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2%3C69::AID-RSA4%3E3.0.CO;2-V"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2491973"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_12"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2209285.2209287"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01415672"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1030.0101"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.07.001"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/646235.682700"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_50"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781315388021"},{"key":"e_1_2_1_38_1","unstructured":"Irit Katriel. 2002. Implicit Data Structures Based on Local Reorganizations. Master\u2019s thesis. Technion--Isreal Inst. of Tech. Haifa.  Irit Katriel. 2002. Implicit Data Structures Based on Local Reorganizations. Master\u2019s thesis. Technion--Isreal Inst. of Tech. Haifa."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/365628.365655"},{"key":"e_1_2_1_40_1","volume-title":"The Art of Computer Programming: Fundamental Algorithms","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1997. The Art of Computer Programming: Fundamental Algorithms ( 3 rd ed.). Vol. 1 . Addison-Wesley . 435--425. Donald E. Knuth. 1997. The Art of Computer Programming: Fundamental Algorithms (3rd ed.). Vol. 1. Addison-Wesley. 435--425.","edition":"3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019325647X"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00175-4"},{"key":"e_1_2_1_43_1","unstructured":"Percona Inc. 2016a. Percona TokuDB. Retrieved from https:\/\/www.percona.com\/software\/mysql-database\/percona-tokudb. (2016).  Percona Inc. 2016a. Percona TokuDB. Retrieved from https:\/\/www.percona.com\/software\/mysql-database\/percona-tokudb. (2016)."},{"key":"e_1_2_1_44_1","unstructured":"Percona Inc. 2016b. Percona TokuMX. Retrieved from https:\/\/www.percona.com\/software\/mongo-database\/percona-tokumx. (2016).  Percona Inc. 2016b. Percona TokuMX. Retrieved from https:\/\/www.percona.com\/software\/mongo-database\/percona-tokumx. (2016)."},{"volume-title":"Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science","author":"Prokop Harald","key":"e_1_2_1_45_1","unstructured":"Harald Prokop . 1999. Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science , Massachusetts Institute of Technology . Harald Prokop. 1999. Cache-Oblivious Algorithms. Master\u2019s thesis. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/321650.321658"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/321832.321846"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/20.3.242"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0381"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_52"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018955111939"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/800200.806206"},{"key":"e_1_2_1_54_1","unstructured":"Jos\u00e9 C. Verschae. 2012. The Power of Recourse in Online Optimization Robust Solutions for Scheduling Matroid and MST Problems The Power of Recourse in Online Optimization: Robust Solutions for Scheduling Matroid and MST Problems. Ph.D. Dissertation. Technischen Universit\u00e4t Berlin.  Jos\u00e9 C. Verschae. 2012. The Power of Recourse in Online Optimization Robust Solutions for Scheduling Matroid and MST Problems The Power of Recourse in Online Optimization: Robust Solutions for Scheduling Matroid and MST Problems. Ph.D. Dissertation. Technischen Universit\u00e4t Berlin."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802183"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16879"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90034-D"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.2307\/2319522"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070693","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3070693","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3070693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:27Z","timestamp":1750217427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,26]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3070693"],"URL":"https:\/\/doi.org\/10.1145\/3070693","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2017,5,26]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}