2026-08-17T23:24:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21154 2024-09-23T09:13:18Z ddc:004 open_access

Scalable Distributed String Sorting Kurpicz, Florian Mehnert, Pascal Sanders, Peter Schimek, Matthias sorting strings distributed-memory computing distributed membership filters scalability String sorting is an important part of tasks such as building index data structures. Unfortunately, current string sorting algorithms do not scale to massively parallel distributed-memory machines since they either have latency (at least) proportional to the number of processors p or communicate the data a large number of times (at least logarithmic). We present practical and efficient algorithms for distributed-memory string sorting that scale to large p. Similar to state-of-the-art sorters for atomic objects, the algorithms have latency of about p^{1/k} when allowing the data to be communicated k times. Experiments indicate good scaling behavior on a wide range of inputs on up to 49152 cores. Overall, we achieve speedups of up to 4.9 over the current state-of-the-art distributed string sorting algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Kurpicz and Pascal Mehnert and Peter Sanders and Matthias Schimek 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.83 urn:nbn:de:0030-drops-211541 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.83 eng https://creativecommons.org/licenses/by/4.0/legalcode