{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:29Z","timestamp":1750308749902,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,11,1]],"date-time":"2009-11-01T00:00:00Z","timestamp":1257033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0702728"],"award-info":[{"award-number":["CCF-0702728"]}],"id":[{"id":"10.13039\/100000143","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":[[2009,11]]},"abstract":"<jats:p>Declustering distributes data among parallel disks to reduce retrieval cost using I\/O parallelism. Many schemes were proposed for single copy declustering of spatial data. Recently, declustering using replication gained a lot of interest and several schemes with different properties were proposed. It is computationally expensive to verify optimality of replication schemes designed for range queries and existing schemes verify optimality for up to 50 disks. In this article, we propose a novel method to find replicated declustering schemes that render all spatial range queries optimal. The proposed scheme uses threshold based declustering, divisibility of large queries for optimization and optimistic approach to compute maximum flow. The proposed scheme is generic and works for any number of dimensions. Experimental results show that using 3 copies there exist allocations that render all spatial range queries optimal for up to 750 disks in 2 dimensions and with the exception of several values for up to 100 disks in 3 dimensions. The proposed scheme improves search for strictly optimal replicated declustering schemes significantly and will be a valuable tool to answer open problems on replicated declustering.<\/jats:p>","DOI":"10.1145\/1629075.1629077","type":"journal-article","created":{"date-parts":[[2009,11,30]],"date-time":"2009-11-30T14:56:36Z","timestamp":1259592996000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Divide-and-conquer scheme for strictly optimal retrieval of range queries"],"prefix":"10.1145","volume":"5","author":[{"given":"Ali \u015eaman","family":"Tosun","sequence":"first","affiliation":[{"name":"University of Texas at San Antonio"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,11,30]]},"reference":[{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 409--418","author":"Abdel-Ghaffar K. A. S.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 329--338","author":"Amer-Yahia S.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/874051.874730"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335224"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253263"},{"volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT). 525--537","author":"Bhatia R.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 271--280","author":"Chen C.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543618"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956871"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182596"},{"volume-title":"Proceedings of the 3rd International ACPC Conference with Special Emphasis on Parallel Databases and Parallel I\/O. 110--123","author":"Ciaccia P.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/319682.319698"},{"volume-title":"Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems. 18--25","author":"Faloutsos C.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73747"},{"volume-title":"Proceedings of the 8th International Parallel Processing Symposium.","author":"Fan C.","key":"e_1_2_1_16_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 608--615","author":"Ferhatosmanoglu H.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-006-9362-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055577"},{"key":"e_1_2_1_20_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_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"volume-title":"Proceedings of the International Conference onVery Large Databases (VLDB). 481--492","year":"1990","author":"Ghandeharizadeh S.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645475.654028"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130293"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 148--161","author":"Gray J.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"volume-title":"Proceedings of the International Conference on Database and Expert System Applications. 401--409","author":"Hua K. A.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.219753"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50221"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2003.08.003"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB)","author":"Li J.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019269409432"},{"key":"e_1_2_1_34_1","unstructured":"Lovasz L. and Plummer M. 1986. Matching Theory. North-Holland.   Lovasz L. and Plummer M. 1986. Matching Theory. North-Holland."},{"volume-title":"Proceedings of the Parallel Processing Symposium.","author":"Moon B.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/645483.653611"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277674"},{"volume-title":"The Design and Analysis of Spatial Structures","author":"Samet H.","key":"e_1_2_1_38_1"},{"volume-title":"Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms.","author":"Sanders P.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(96)00024-5"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Sinha R. K. Bhatia R. and Chen C. 2001. Asymptotically optimal declustering schemes for range queries. In Proceedings of the 8th International Conference on Database Theory. Lecture Notes in Computer Science. Springer 144--158.   Sinha R. K. Bhatia R. and Chen C. 2001. Asymptotically optimal declustering schemes for range queries. In Proceedings of the 8th International Conference on Database Theory. Lecture Notes in Computer Science. Springer 144--158.","DOI":"10.1007\/3-540-44503-X_10"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/648315.756320"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/967900.968054"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITCC.2005.112"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITCC.2005.124"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11546924_80"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-006-8484-0"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.1082"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2006.08.011"},{"volume-title":"Proceedings of the International Workshops on Parallel Processing (ICPP)","author":"Tosun A. S.","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.2002.1029710"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1629075.1629077","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1629075.1629077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:19Z","timestamp":1750278139000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1629075.1629077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["10.1145\/1629075.1629077"],"URL":"https:\/\/doi.org\/10.1145\/1629075.1629077","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2009,11]]},"assertion":[{"value":"2008-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}