KIT | KIT-Bibliothek | Impressum | Datenschutz

Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools

Bingmann, Timo

This dissertation focuses on two fundamental sorting problems: string sorting and suffix sorting. The first part considers parallel string sorting on shared-memory multi-core machines, the second part external memory suffix sorting using the induced sorting principle, and the third part distributed external memory suffix sorting with a new distributed algorithmic big data framework named Thrill.
Sorting strings or vectors is a basic algorithmic challenge different from integer sorting because it is important to access components of the keys to avoid repeated operations on the entire string. We focus on sorting large inputs which fit into the RAM of a shared-memory machine. String sorting is needed for instance in database index construction, suffix sorting algorithms, and to order high-dimensional geometric data.
We first survey engineered variants of basic sequential string sorting algorithms and perform an extensive experimental evaluation to measure their performance. Furthermore, we perform experiments to quantify parallel memory bandwidth and latency experiments as preliminary work for designing parallel string sorting algori ... mehr

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000085031
Veröffentlicht am 03.08.2018
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2018
Sprache Englisch
Identifikator urn:nbn:de:swb:90-850313
KITopen-ID: 1000085031
Verlag KIT, Karlsruhe
Umfang XXI, 374 S.
Abschlussart Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 03.07.2018
Referent/Betreuer Prof. P. Sanders
Schlagworte string sorting, suffix sorting, parallel algorithms, distributed computing
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page