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 algorithms.
... mehr

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