2026-09-19T04:52:08Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/98144 2023-07-11 col_2142_10761 col_2142_5131 com_2142_10755 com_2142_234 com_2142_5130

The student, - Vipul Harsh, submitted this Thesis for approval on 2017-07-04 at 08:53. This Thesis was approved for publication on 2017-07-05 at 11:51. Kale, Laxmikant Vipul Harsh, - 2017-09-29T16:38:08Z 2017-09-29T16:38:08Z 2017-07-05 2017-08 Standard parallel sorting algorithms like sample sort rely on data partitioning techniques to distribute keys across processors. The sampling cost in sample sort for good load balance is prohibitive for massive clusters. We describe Histogram sort with sampling, an adaptation of the popular Histogram sort algorithm. We show that Histogram sort with sampling has sound theoretical guarantees and reduces the sample size requirements from O(p log N/epsilon^2) to O(k p sqrt[k]{log p/epsilon}) with k rounds of histogramming w.h.p.. Histogram sort with sampling is more efficient than Sample sort algorithms that achieve the same level of load balance, both in theory and practice, especially for massively parallel applications, scaling to tens of thousands of processors. We also show that an approximate but fairly accurate histogram can be obtained using a O( sqrt {p log N}/epsilon) sample on every processor. This can be used to speed up the histogramming step and can be of independent interest for answering general queries in large parallel processing systems. In our practical implementation, we exploit shared memory within nodes to improve the performance of our algorithm on large modern clusters. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo terms The student, - Vipul Harsh, accepted the attached license on 2017-07-04 at 08:52. DSpace SAF Submission Ingestion Package generated from Vireo submission #11293 on 2017-09-29 at 11:27:35 Made available in DSpace on 2017-09-29T16:38:08Z (GMT). No. of bitstreams: 2 VIPULHARSH-THESIS-2017.pdf: 518495 bytes, checksum: 7d795ecec72494bd4a71300996d87591 (MD5) LICENSE.txt: 4210 bytes, checksum: b79e8d9a70455cc23001c8def0a12833 (MD5) Previous issue date: 2017-07-05 application/pdf http://hdl.handle.net/2142/98144 en Copyright 2017 Vipul Harsh Parallel sorting Data partitioning Sample sort Histogram sort Histogram sort with sampling text text Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.