{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:33Z","timestamp":1750220673848,"version":"3.41.0"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["807\/20"],"award-info":[{"award-number":["807\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"<jats:p>Deduplication decreases the physical occupancy of files in a storage volume by removing duplicate copies of data chunks, but creates data-sharing dependencies that complicate standard storage management tasks. Specifically, data migration plans must consider the dependencies between files that are remapped to new volumes and files that are not. Thus far, only greedy approaches have been suggested for constructing such plans, and it is unclear how they compare to one another and how much they can be improved.<\/jats:p>\n          <jats:p>\n            We set to bridge this gap for\n            <jats:italic>seeding<\/jats:italic>\n            \u2014migration in which the target volume is initially empty. We prove that even this basic instance of data migration is NP-hard in the presence of deduplication. We then present GoSeed, a formulation of seeding as an integer linear programming (ILP) problem, and three acceleration methods for applying it to real-sized storage volumes. Our experimental evaluation shows that, while the greedy approaches perform well on \u201ceasy\u201d problem instances, the cost of their solution can be significantly higher than that of GoSeed\u2019s solution on \u201chard\u201d instances, for which they are sometimes unable to find a solution at all.\n          <\/jats:p>","DOI":"10.1145\/3453301","type":"journal-article","created":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T00:10:00Z","timestamp":1629159000000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["GoSeed: Optimal Seeding Plan for Deduplicated Storage"],"prefix":"10.1145","volume":"17","author":[{"given":"Aviv","family":"Nachman","sequence":"first","affiliation":[{"name":"Computer Science Department, Technion, Haifa, Israel"}]},{"given":"Sarai","family":"Sheinvald","sequence":"additional","affiliation":[{"name":"ORT Braude College of Engineering, Carmiel, Israel"}]},{"given":"Ariel","family":"Kolikant","sequence":"additional","affiliation":[{"name":"Computer Science Department, Technion, Haifa, Israel"}]},{"given":"Gala","family":"Yadgar","sequence":"additional","affiliation":[{"name":"Computer Science Department, Technion, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2021,8,16]]},"reference":[{"volume-title":"Retrieved on","year":"2019","author":"Optimizer CPLEX","key":"e_1_2_1_1_1"},{"volume-title":"Gurobi. Retrieved on","year":"2019","key":"e_1_2_1_2_1"},{"volume-title":"Retrieved on","year":"2019","author":"Linear Programming GLPK","key":"e_1_2_1_3_1"},{"volume-title":"Free Software Foundation. Retrieved on","year":"2019","key":"e_1_2_1_4_1"},{"volume-title":"SNIA. Retrieved on","year":"2019","key":"e_1_2_1_5_1"},{"volume-title":"Retrieved on","year":"2019","author":"Ladanyi Laszlo","key":"e_1_2_1_6_1"},{"volume-title":"Traces and Snapshots Public Archive. File systems and Storage Lab (FSL)","year":"2019","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/inte.19.4.20"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855711.1855739"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277355.3277423"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/647258.720796"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1973333.1973346"},{"volume-title":"Ergastulum: Quickly Finding Near-optimal Storage System Designs. HP Laboratories.","year":"2002","author":"Anderson Eric","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535929"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MASCOT.2009.5366623"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1960475.1960481"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674025.2576204"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855807.1855815"},{"volume-title":"Linear Programming and Extensions","author":"Dantzig George B.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855840.1855856"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1960475.1960477"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208488.2208501"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3129633.3129637"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1525908.1525923"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3358807.3358862"},{"volume-title":"INTRODUCTION TO THE EMC XtremIO STORAGE ARRAY (Ver. 4.0) (rev. 08 ed.)","year":"2016","author":"EMC Corporation 2015.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2013.6558437"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2643634.2643653"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2750482.2750507"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2002181.2002206"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1960475.1960482"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855763"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3323298.3323309"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2930583.2930604"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.187"},{"volume-title":"23rd IEEE Symposium on Mass Storage Systems and Technologies (MSST\u201906)","author":"Charles","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2367589.2367600"},{"volume-title":"Complexity of Computer Computations","author":"Karp R.","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2643634.2643686"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.284"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591272.2591292"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1525908.1525917"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2591305.2591330"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1973333.1973351"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1267074.1267076"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211890.3211894"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389006"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1960475.1960476"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/502059.502052"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/3386691.3386710"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485732.2485744"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC.2011.82"},{"key":"e_1_2_1_53_1","volume-title":"American Control Conference","volume":"3","author":"Richards A.","year":"1936"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2287076.2287081"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026852.3026870"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208461.2208485"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1456469.1456471"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1364813.1364834"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2016.7897080"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/2342821.2342845"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/2002181.2002196"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844146"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208461.2208465"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/3189759.3189790"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.07.016"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026959.3026969"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026852.3026872"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1109\/CC.2016.7559071","article-title":"Efficient algorithm for k-barrier coverage based on integer linear programming","volume":"13","author":"Zhang Yanhua","year":"2016","journal-title":"China Commun."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/3189759.3189789"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/1364813.1364831"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39611-3_16"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453301","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:06Z","timestamp":1750197786000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,16]]},"references-count":71,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3453301"],"URL":"https:\/\/doi.org\/10.1145\/3453301","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2021,8,16]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}