KIT | KIT-Bibliothek | Impressum | Datenschutz

Communication-Efficient Probabilistic Algorithms: Selection, Sampling, and Checking

Hübschle-Schneider, Lorenz

Abstract:
Diese Dissertation behandelt drei grundlegende Klassen von Problemen in Big-Data-Systemen, für die wir kommunikationseffiziente probabilistische Algorithmen entwickeln. Im ersten Teil betrachten wir verschiedene Selektionsprobleme, im zweiten Teil das Ziehen gewichteter Stichproben (Weighted Sampling) und im dritten Teil die probabilistische Korrektheitsprüfung von Basisoperationen in Big-Data-Frameworks (Checking). Diese Arbeit ist durch einen wachsenden Bedarf an Kommunikationseffizienz motiviert, der daher rührt, dass der auf das Netzwerk und seine Nutzung zurückzuführende Anteil sowohl der Anschaffungskosten als auch des Energieverbrauchs von Supercomputern und der Laufzeit verteilter Anwendungen immer weiter wächst. ... mehr

Abstract (englisch):
This dissertation focuses on three fundamental problem families in big data systems, for which we develop communication-efficient probabilistic algorithms. In the first part, we consider various selection problems, in the second, weighted sampling problems, and the third, checking of basic operations in big data systems. This is motivated by a growing need for communication efficiency as the network and its usage increasingly dominate supercomputer system cost and energy consumption as well as running times of distributed applications. Surprisingly few communication-efficient algorithms are known for fundamental big data problems, and we close several of these gaps.
... mehr

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000127719
Veröffentlicht am 17.12.2020
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsdatum 17.12.2020
Sprache Englisch
Identifikator KITopen-ID: 1000127719
Verlag Karlsruher Institut für Technologie (KIT)
Umfang XIII, 177 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 26.11.2020
Referent/Betreuer Prof. P. Sanders
Schlagwörter communication efficiency, distributed algorithms, probabilistic algorithms, big data, selection, frequent items, sampling, weighted sampling, reservoir sampling, checking, probabilistic verification
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page