{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T17:58:55Z","timestamp":1648663135366},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,12]]},"abstract":"<jats:p> In this paper we show the power of sampling techniques in designing efficient distributed algorithms. In particular, we apply sampling techniques in the design of selection algorithms on the hypercube and de Bruijn networks, and show that the message complexity of selecting an item from a set (file) is less sensitive to the cardinality of the set (file). Given a file with n keys, our algorithm performs a selection on a p-node de Bruijn network or hypercube using only O(p log log n) messages and suffering a delay of O(\u03c4 log p log log n), with high probability. Our selection scheme outperforms the existing approaches in terms of both message complexity and communication delay. Because of the lesser sensitivity of message complexity and communication delay of our algorithms to the file size, our distributed selection schemes are very attractive in applications where very large database systems are involved. Using our selection algorithms, we also show that both quicksort-based sorting scheme and enumeration sorting scheme can be developed for sorting large distributed files on the hypercube and de Bruijn networks. Both of our sorting algorithms outperform the existing distributed sorting schemes in terms of both message complexity and communication delay. <\/jats:p>","DOI":"10.1142\/s0129054103002229","type":"journal-article","created":{"date-parts":[[2003,12,19]],"date-time":"2003-12-19T00:51:21Z","timestamp":1071795081000},"page":"1129-1146","source":"Crossref","is-referenced-by-count":0,"title":["EFFICIENT ALGORITHMS FOR SELECTION AND SORTING OF LARGE DISTRIBUTED  FILES ON DE BRUIJN AND HYPERCUBE STRUCTURES"],"prefix":"10.1142","volume":"14","author":[{"given":"DAVID S. L.","family":"WEI","sequence":"first","affiliation":[{"name":"Dept. of Comp. and Info. Sc.,  Fordham University, Bronx, NY 10458, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SANGUTHEVAR","family":"RAJASEKARAN","sequence":"additional","affiliation":[{"name":"Dept. of Comp. and Info. Sc.,  University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KSHIRASAGAR","family":"NAIK","sequence":"additional","affiliation":[{"name":"Dept. of Elect. and Comp. Eng.,  University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SY-YEN","family":"KUO","sequence":"additional","affiliation":[{"name":"Dept. of Elect. Eng.,  National Taiwan University, Taipei, Taiwan, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51687-5"},{"key":"rf4","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"1991"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360691"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(90)90081-N"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1109\/71.329670"},{"key":"rf10","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, and Hypercubes","author":"Leighton F. T.","year":"1992"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"rf12","first-page":"642","author":"Nassimi D.","journal-title":"JACM"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1109\/90.392386"},{"key":"rf14","volume":"20","author":"Palis M.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-585-27330-3_6"},{"key":"rf17","unstructured":"S.\u00a0Rajasekaran and S.\u00a0Sen, Synthesis of Parallel Algorithms, ed. J. H.\u00a0Reif (Morgan-Kaufman Publishers, 1993)\u00a0pp. 411\u2013451."},{"key":"rf18","first-page":"372","volume":"34","author":"Rotem D.","journal-title":"IEEE Trans. on Computers"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90368-P"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0020419"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1145\/263932.263939"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103002229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:26:04Z","timestamp":1565177164000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103002229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":17,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,12]]}},"alternative-id":["10.1142\/S0129054103002229"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103002229","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}