{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/98144"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/98144","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Histogram sort with sampling","abstract":"The student, - Vipul Harsh, submitted this Thesis for approval on 2017-07-04 at 08:53.","abstract_html":"The student, - Vipul Harsh, submitted this Thesis for approval on 2017-07-04 at 08:53.","abstract_has_math":false,"creators":["Vipul Harsh, -"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Kale, Laxmikant"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-09-29T16:38:08Z","date_published":"2017-09-29T16:38:08Z","updated_at":"2026-07-22T22:24:35Z","subjects":["Parallel sorting","Data partitioning","Sample sort","Histogram sort"],"languages":["en"],"rights":["Copyright 2017 Vipul Harsh"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/98144","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kale, Laxmikant"]},{"key":"dc:creator","label":"Author","values":["Vipul Harsh, -"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-09-29T16:38:08Z","2017-07-05","2017-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Parallel sorting","Data partitioning","Sample sort","Histogram sort"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Vipul Harsh"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/98144"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","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"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Histogram sort with sampling"]}]}],"canonical_facts":{"dc:contributor":["Kale, Laxmikant"],"dc:creator":["Vipul Harsh, -"],"dc:date":["2017-09-29T16:38:08Z","2017-07-05","2017-08"],"dc:description":["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.","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"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/98144"],"dc:language":["en"],"dc:rights":["Copyright 2017 Vipul Harsh"],"dc:subject":["Parallel sorting","Data partitioning","Sample sort","Histogram sort"],"dc:title":["Histogram sort with sampling"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:35Z"}