{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:09Z","timestamp":1775282289579,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            Parallel independent disks can enhance the performance of external memory (EM) algorithms, but the programming task is often difficult. Each disk can service only one read or write request at a time; the challenge is to keep the disks as busy as possible. In this article, we develop a randomized allocation discipline for parallel independent disks, called\n            <jats:italic>randomized cycling<\/jats:italic>\n            . We show how it can be used as the basis for an efficient distribution sort algorithm, which we call\n            <jats:italic>randomized cycling distribution sort<\/jats:italic>\n            (RCD). We prove that the expected I\/O complexity of RCD is optimal. The analysis uses a novel reduction to a scenario with significantly fewer probabilistic interdependencies. We demonstrate RCD's practicality by experimental simulations. Using the randomized cycling discipline, algorithms developed for the unrealistic multihead disk model can be simulated on the realistic parallel disk model for the class of\n            <jats:italic>multipass<\/jats:italic>\n            algorithms, which make a complete pass through their data before accessing any element a second time. In particular, algorithms based upon the well-known distribution and merge paradigms of EM computation can be optimally extended from a single disk to parallel disks.\n          <\/jats:p>","DOI":"10.1145\/1162349.1162352","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"656-680","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Distribution sort with randomized cycling"],"prefix":"10.1145","volume":"53","author":[{"given":"Jeffrey Scott","family":"Vitter","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, IN"}]},{"given":"David Alexander","family":"Hutchinson","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Ont., Canada"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Conference on Very Large Databases","volume":"24","author":"Arge L."},{"key":"e_1_2_1_3_1","unstructured":"Arge L. Vengroff D. E. and Vitter J. S. 2007. External-memory algorithms for processing line segments in geographic information systems. Algorithmica. to appear. 10.1007\/s00453-006-1208-z   Arge L. Vengroff D. E. and Vitter J. S. 2007. External-memory algorithms for processing line segments in geographic information systems. Algorithmica. to appear. 10.1007\/s00453-006-1208-z"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240481X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(97)00015-X"},{"key":"e_1_2_1_6_1","first-page":"2","article-title":"A simple and efficient parallel disk mergesort","volume":"35","author":"Barve R. D.","year":"2002","journal-title":"ACM Trans. Comput. Syst."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s00453-002-1009-y","article-title":"Efficient external memory algorithms by simulating coarse-grained parallel algorithms","volume":"36","author":"Dehne F.","year":"2003","journal-title":"Algorithmica"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/s00224-002-1066-2","article-title":"Bulk synchronous parallel algorithms for the external memory model","volume":"35","author":"Dehne F.","year":"2002","journal-title":"Theory Comput. Syst."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2%3C99::AID-RSA1%3E3.0.CO;2-M"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science.","author":"Goodrich M. T."},{"key":"e_1_2_1_11_1","volume-title":"Tech. Rep. 1998--011","author":"Henzinger M. R.","year":"1998"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703431573"},{"key":"e_1_2_1_13_1","volume-title":"The Art of Computer Programming","volume":"3","author":"Knuth D. E.","year":"1998"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM Symposium on Parallel Algorithms and Architectures.","author":"Nodine M. H."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210343"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Sanders P."},{"key":"e_1_2_1_17_1","unstructured":"TPIE 1999. TPIE user manual and reference. The manual and software distribution are available on the web at http:\/\/www.cs.duke.edu\/TPIE\/.  TPIE 1999. TPIE user manual and reference. The manual and software distribution are available on the web at http:\/\/www.cs.duke.edu\/TPIE\/."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the DAGS Symposium on Parallel Computation","author":"Vengroff D. E.","year":"1994"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IEEE Symposium on Parallel and Distributed Processing. IEEE Computer Society Press, Los Alamitos, CA","author":"Vengroff D. E."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_21_1","first-page":"431","article-title":"Average-case analysis of algorithms and data structures. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, J. van Leeuwen, Ed. Elsevier and MIT Press","volume":"9","author":"Vitter J. S.","year":"1990","journal-title":"Chap."},{"key":"e_1_2_1_22_1","first-page":"2","article-title":"Algorithms for parallel memory I: Two-level memories","volume":"12","author":"Vitter J. S.","year":"1994","journal-title":"Algorithmica"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1162349.1162352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:56:19Z","timestamp":1672257379000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1162349.1162352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1162349.1162352"],"URL":"https:\/\/doi.org\/10.1145\/1162349.1162352","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}