{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/115736"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/115736","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimal round and sample-size complexity for partitioning in parallel sorting","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-05-01","abstract_has_math":false,"creators":["Yang, Wentao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Solomonik, Edgar"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-05","date_published":"2022-05","updated_at":"2026-07-22T22:24:55Z","subjects":["parallel sorting","data partitioning"],"languages":["en","eng"],"rights":["Copyright 2022 Wentao Yang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/115736","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Solomonik, Edgar"]},{"key":"dc:creator","label":"Author","values":["Yang, Wentao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-05","2022-04-28"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"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"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Wentao Yang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/115736"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-05-01","The student, Wentao Yang, accepted the attached license on 2022-04-28 at 00:17.","The student, Wentao Yang, submitted this Thesis for approval on 2022-04-28 at 00:26.","This Thesis was approved for publication on 2022-04-28 at 09:16.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17684 on 2022-11-11 at 12:57:58","State-of-the-art parallel sorting algorithms for distributed-memory architectures are based on computing a balanced partitioning via sampling and histogramming. By finding samples that partition the sorted keys into evenly-sized chunks, these algorithms minimize the number of communication rounds required. Histogramming (computing positions of samples) guides sampling, enabling a decrease in the overall number of samples collected. We derive lower and upper bounds on the number of sampling/histogramming rounds required to compute a balanced partitioning. We improve on prior results to demonstrate that when using p processors/parts, O(log∗ p) rounds with O(p/ log∗ p) samples per round suffice. We match that with a lower bound that shows any algorithm requires at least Ω(log∗ p) rounds with O(p) samples per round. Additionally, we prove the Ω(p log p) samples lower bound for one round, showing the optimality of sample sort in this case. To derive the lower bound, we propose a hard randomized input distribution and apply classical results from the distribution theory of runs."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Optimal round and sample-size complexity for partitioning in parallel sorting"]}]}],"canonical_facts":{"dc:contributor":["Solomonik, Edgar"],"dc:creator":["Yang, Wentao"],"dc:date":["2022-05","2022-04-28"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-05-01","The student, Wentao Yang, accepted the attached license on 2022-04-28 at 00:17.","The student, Wentao Yang, submitted this Thesis for approval on 2022-04-28 at 00:26.","This Thesis was approved for publication on 2022-04-28 at 09:16.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17684 on 2022-11-11 at 12:57:58","State-of-the-art parallel sorting algorithms for distributed-memory architectures are based on computing a balanced partitioning via sampling and histogramming. By finding samples that partition the sorted keys into evenly-sized chunks, these algorithms minimize the number of communication rounds required. Histogramming (computing positions of samples) guides sampling, enabling a decrease in the overall number of samples collected. We derive lower and upper bounds on the number of sampling/histogramming rounds required to compute a balanced partitioning. We improve on prior results to demonstrate that when using p processors/parts, O(log∗ p) rounds with O(p/ log∗ p) samples per round suffice. We match that with a lower bound that shows any algorithm requires at least Ω(log∗ p) rounds with O(p) samples per round. Additionally, we prove the Ω(p log p) samples lower bound for one round, showing the optimality of sample sort in this case. To derive the lower bound, we propose a hard randomized input distribution and apply classical results from the distribution theory of runs."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/115736"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Wentao Yang"],"dc:subject":["parallel sorting","data partitioning"],"dc:title":["Optimal round and sample-size complexity for partitioning in parallel sorting"],"dc:type":["text","Thesis"],"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:55Z"}