{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:19:25Z","timestamp":1750306765524,"version":"3.41.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,7,1]],"date-time":"2013-07-01T00:00:00Z","timestamp":1372636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0855247"],"award-info":[{"award-number":["CNS-0855247"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2013,7]]},"abstract":"<jats:p>Declustering techniques reduce query response times through parallel I\/O by distributing data among parallel disks. Recently, replication-based approaches were proposed to further reduce the response time. Efficient retrieval of replicated data from multiple disks is a challenging problem. Existing retrieval techniques are designed for storage arrays with identical disks, having no initial load or network delay. In this article, we consider the generalized retrieval problem of replicated data where the disks in the system might be heterogeneous, the disks may have initial load, and the storage arrays might be located on different sites. We first formulate the generalized retrieval problem using a Linear Programming (LP) model and solve it with mixed integer programming techniques. Next, the generalized retrieval problem is formulated as a more efficient maximum flow problem. We prove that the retrieval schedule returned by the maximum flow technique yields the optimal response time and this result matches the LP solution. We also propose a low-complexity online algorithm for the generalized retrieval problem by not guaranteeing the optimality of the result. Performance of proposed and state of the art retrieval strategies are investigated using various replication schemes, query types, query loads, disk specifications, network delays, and initial loads.<\/jats:p>","DOI":"10.1145\/2491472.2491474","type":"journal-article","created":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T19:12:41Z","timestamp":1374779561000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Generalized Optimal Response Time Retrieval of Replicated Data from Storage Arrays"],"prefix":"10.1145","volume":"9","author":[{"given":"Nihat","family":"Altiparmak","sequence":"first","affiliation":[{"name":"University of Texas at San Antonio"}]},{"given":"Ali \u015eaman","family":"Tosun","sequence":"additional","affiliation":[{"name":"University of Texas at San Antonio"}]}],"member":"320","published-online":{"date-parts":[[2013,7]]},"reference":[{"volume-title":"Proceedings of ICDT. 409--418","author":"Abdel-Ghaffar K. A. S.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","unstructured":"Adaptec. 2010. Adaptec high-performance hybrid arrays (HPHAs). http:\/\/www.adaptec.com\/nr\/rdonlyres\/a1c72763-e3b9-45f7-b871-a490c29a9b11\/0\/hpha5_fb.pdf. PMC-Sierra Inc.  Adaptec. 2010. Adaptec high-performance hybrid arrays (HPHAs). http:\/\/www.adaptec.com\/nr\/rdonlyres\/a1c72763-e3b9-45f7-b871-a490c29a9b11\/0\/hpha5_fb.pdf. PMC-Sierra Inc."},{"volume-title":"Proceedings of Usenix Annual Technical Conference (ATC). 57--70","author":"Agrawal N.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.177"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/140901.140919"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335224"},{"volume-title":"Proceedings of ISCA PDCS. 41--48","author":"Bader D. A.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"volume-title":"Proceedings of EDBT. 525--537","author":"Bhatia R.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543618"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956871"},{"volume-title":"Proceedings of ICDE. 271--280","author":"Chen C.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182596"},{"key":"e_1_2_1_14_1","unstructured":"CPLEX I. IBM ilog cplex optimization studio for academics: High-performance software for mathematical programming and optimization. http:\/\/www.ilog.com\/products\/cplex\/.  CPLEX I. IBM ilog cplex optimization studio for academics: High-performance software for mathematical programming and optimization. http:\/\/www.ilog.com\/products\/cplex\/."},{"key":"e_1_2_1_15_1","unstructured":"Dantzig G. B. and Thapa M. N. 1997. Linear Programming 1: Introduction. Springer-Verlag.   Dantzig G. B. and Thapa M. N. 1997. Linear Programming 1: Introduction. Springer-Verlag."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/319682.319698"},{"key":"e_1_2_1_17_1","unstructured":"EqualLogic. 2011. Equallogic ps6100xs hybrid storage array. http:\/\/www.equallogic.com\/products\/default.aspx?id=10653. Dell Inc.  EqualLogic. 2011. Equallogic ps6100xs hybrid storage array. http:\/\/www.equallogic.com\/products\/default.aspx?id=10653. Dell Inc."},{"volume-title":"Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems. 18--25","author":"Faloutsos C.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the 8th International Parallel Processing Symposium.","author":"Fan C.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055577"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_10"},{"volume-title":"Proceedings of the 13th International Conference on Database and Expert Systems Applications (DEXA). 669--678","author":"Frikken K.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"volume-title":"Proceedings of VLDB. 481--492","author":"Ghandeharizadeh S.","key":"e_1_2_1_24_1"},{"volume-title":"Proceedings of ICDE. 466--475","author":"Ghandeharizadeh S.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2010.156"},{"volume-title":"Proceedings of Database and Expert System Applications. 401--409","author":"Hua K. A.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"volume-title":"Proceedings of the IEEE International Symposium on Workload Characterization (IISWC). 119--128","author":"Kavalanekar S.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.219753"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50221"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2003.08.003"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019269409432"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/204865.204889"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"volume-title":"Everest: Scaling down peak loads through I\/O off-loading. In Oper. Syst. Design Implement. 15--28.","year":"2008","author":"Narayanan D.","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519081"},{"key":"e_1_2_1_40_1","unstructured":"Nimbus. 2010. Nimbus data s-class enterprise flash storage systems. http:\/\/www.nimbusdata.com\/products\/Nimbus_S-class_Datasheet.pdf.  Nimbus. 2010. Nimbus data s-class enterprise flash storage systems. http:\/\/www.nimbusdata.com\/products\/Nimbus_S-class_Datasheet.pdf."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03869-3_37"},{"volume-title":"IP Storage Networking: Straight to the Core","author":"Orenstein G.","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/645483.653611"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277674"},{"key":"e_1_2_1_45_1","unstructured":"Ramsan. 2010. Ramsan-630 flash solid state disk. http:\/\/www.ramsan.com\/files\/download\/212. White Paper Texas Memory Systems.  Ramsan. 2010. Ramsan-630 flash solid state disk. http:\/\/www.ramsan.com\/files\/download\/212. White Paper Texas Memory Systems."},{"volume-title":"The Design and Analysis of Spatial Structures","author":"Samet H.","key":"e_1_2_1_46_1"},{"volume-title":"Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms.","author":"Sanders P.","key":"e_1_2_1_47_1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(96)00024-5"},{"key":"e_1_2_1_49_1","unstructured":"SNIA. Iotta repository. http:\/\/iotta.snia.org. Storage Networking Ind. Assoc.  SNIA. Iotta repository. http:\/\/iotta.snia.org. Storage Networking Ind. Assoc."},{"key":"e_1_2_1_50_1","unstructured":"Sun. 2009a. Sun storage 7000 unified storage systems family. http:\/\/www.oracle.com\/us\/products\/servers-storage\/039224.pdf.  Sun. 2009a. Sun storage 7000 unified storage systems family. http:\/\/www.oracle.com\/us\/products\/servers-storage\/039224.pdf."},{"key":"e_1_2_1_51_1","unstructured":"Sun. 2009b. Sun storage f5100 flash array. http:\/\/www.oracle.com\/us\/043970.pdf.  Sun. 2009b. Sun storage f5100 flash array. http:\/\/www.oracle.com\/us\/043970.pdf."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/967900.968054"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITCC.2005.112"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITCC.2005.124"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/11546924_80"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.1082"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2006.08.011"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.72"},{"volume-title":"Proceedings of International Workshops on Parallel Processing (ICPP). 506--513","author":"Tosun A. S.","key":"e_1_2_1_59_1"},{"key":"e_1_2_1_60_1","unstructured":"Violin. 2010. Violin 3200 flash memory array. http:\/\/www.violin-memory.com\/assets\/3200-datasheet.pdf. Violin 3200 Memory Datasheet.  Violin. 2010. Violin 3200 flash memory array. http:\/\/www.violin-memory.com\/assets\/3200-datasheet.pdf. Violin 3200 Memory Datasheet."},{"key":"e_1_2_1_61_1","unstructured":"Violin. 2011. Violin 6000 flash memory array. http:\/\/www.violin-memory.com\/assets\/Violin_Datasheet_6000.pdf?d=1. Violin 6000 Memory Datasheet.  Violin. 2011. Violin 6000 flash memory array. http:\/\/www.violin-memory.com\/assets\/Violin_Datasheet_6000.pdf?d=1. Violin 6000 Memory Datasheet."},{"key":"e_1_2_1_62_1","unstructured":"XO. Dedicated Internet access overview. http:\/\/www.xo.com\/services\/network\/dia\/Pages\/overview. aspx. XO Communications LLC.  XO. Dedicated Internet access overview. http:\/\/www.xo.com\/services\/network\/dia\/Pages\/overview. aspx. XO Communications LLC."},{"key":"e_1_2_1_63_1","unstructured":"Zebi. 2012. Zebi hybrid storage array. http:\/\/tegile.biz\/wp-content\/uploads\/2012\/01\/Zebi-White-Paper-012612-Final.pdf. Tegile Systems Inc.  Zebi. 2012. Zebi hybrid storage array. http:\/\/tegile.biz\/wp-content\/uploads\/2012\/01\/Zebi-White-Paper-012612-Final.pdf. Tegile Systems Inc."}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491472.2491474","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2491472.2491474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:49Z","timestamp":1750231729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491472.2491474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["10.1145\/2491472.2491474"],"URL":"https:\/\/doi.org\/10.1145\/2491472.2491474","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2013,7]]},"assertion":[{"value":"2012-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}