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Überraschend wenige kommunikationseffiziente Algorithmen sind für grundlegende Big-Data-Probleme bekannt. In dieser Arbeit schließen wir einige dieser Lücken.
Zunächst betrachten wir verschiedene Selektionsprobleme, beginnend mit der verteilten Version des klassischen Selektionsproblems, d. h. dem Auffinden des Elements von Rang $k$ in einer großen verteilten Eingabe. Wir zeigen, wie dieses Problem kommunikationseffizient gelöst werden kann, ohne anzunehmen, dass die Elemente der Eingabe zufällig verteilt seien. Hierzu ersetzen wir die Methode zur Pivotwahl in einem schon lange bekannten Algorithmus und zeigen, dass dies hinreichend ist. Anschließend zeigen wir, dass die Selektion aus lokal sortierten Folgen – multisequence selection – wesentlich schneller lösbar ist, wenn der genaue Rang des Ausgabeelements in einem gewissen Bereich variieren darf. Dies benutzen wir anschließend, um eine verteilte Prioritätswarteschlange mit Bulk-Operationen zu konstruieren. Später werden wir diese verwenden, um gewichtete Stichproben aus Datenströmen zu ziehen (Reservoir Sampling). Schließlich betrachten wir das Problem, die global häufigsten Objekte sowie die, deren zugehörige Werte die größten Summen ergeben, mit einem stichprobenbasierten Ansatz zu identifizieren.
Im Kapitel über gewichtete Stichproben werden zunächst neue Konstruktionsalgorithmen für eine klassische Datenstruktur für dieses Problem, sogenannte Alias-Tabellen, vorgestellt. Zu Beginn stellen wir den ersten Linearzeit-Konstruktionsalgorithmus für diese Datenstruktur vor, der mit konstant viel Zusatzspeicher auskommt. Anschließend parallelisieren wir diesen Algorithmus für Shared Memory und erhalten so den ersten parallelen Konstruktionsalgorithmus für Aliastabellen. Hiernach zeigen wir, wie das Problem für verteilte Systeme mit einem zweistufigen Algorithmus angegangen werden kann. Anschließend stellen wir einen ausgabesensitiven Algorithmus für gewichtete Stichproben mit Zurücklegen vor. Ausgabesensitiv bedeutet, dass die Laufzeit des Algorithmus sich auf die Anzahl der eindeutigen Elemente in der Ausgabe bezieht und nicht auf die Größe der Stichprobe. Dieser Algorithmus kann sowohl sequentiell als auch auf Shared-Memory-Maschinen und verteilten Systemen eingesetzt werden und ist der erste derartige Algorithmus in allen drei Kategorien. Wir passen ihn anschließend an das Ziehen gewichteter Stichproben ohne Zurücklegen an, indem wir ihn mit einem Schätzer für die Anzahl der eindeutigen Elemente in einer Stichprobe mit Zurücklegen kombinieren. Poisson-Sampling, eine Verallgemeinerung des Bernoulli-Sampling auf gewichtete Elemente, kann auf ganzzahlige Sortierung zurückgeführt werden, und wir zeigen, wie ein bestehender Ansatz parallelisiert werden kann. Für das Sampling aus Datenströmen passen wir einen sequentiellen Algorithmus an und zeigen, wie er in einem Mini-Batch-Modell unter Verwendung unserer im Selektionskapitel eingeführten Bulk-Prioritätswarteschlange parallelisiert werden kann. Das Kapitel endet mit einer ausführlichen Evaluierung unserer Aliastabellen-Konstruktionsalgorithmen, unseres ausgabesensitiven Algorithmus für gewichtete Stichproben mit Zurücklegen und unseres Algorithmus für gewichtetes Reservoir-Sampling.
Um die Korrektheit verteilter Algorithmen probabilistisch zu verifizieren, schlagen wir Checker für grundlegende Operationen von Big-Data-Frameworks vor. Wir zeigen, dass die Überprüfung zahlreicher Operationen auf zwei „Kern“-Checker reduziert werden kann, nämlich die Prüfung von Aggregationen und ob eine Folge eine Permutation einer anderen Folge ist. Während mehrere Ansätze für letzteres Problem seit geraumer Zeit bekannt sind und sich auch einfach parallelisieren lassen, ist unser Summenaggregations-Checker eine neuartige Anwendung der gleichen Datenstruktur, die auch zählenden Bloom-Filtern und dem Count-Min-Sketch zugrunde liegt. Wir haben beide Checker in Thrill, einem Big-Data-Framework, implementiert. Experimente mit absichtlich herbeigeführten Fehlern bestätigen die von unserer theoretischen Analyse vorhergesagte Erkennungsgenauigkeit. Dies gilt selbst dann, wenn wir häufig verwendete schnelle Hash-Funktionen mit in der Theorie suboptimalen Eigenschaften verwenden. Skalierungsexperimente auf einem Supercomputer zeigen, dass unsere Checker nur sehr geringen Laufzeit-Overhead haben, welcher im Bereich von $2\,\%$ liegt und dabei die Korrektheit des Ergebnisses nahezu garantiert wird.
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
We first consider different selection problems, starting with selecting the element with rank $k$ from a large, distributed input. There, we show how this can be achieved without assuming a random distribution of the input by redesigning the pivot selection step. Next, we show that selection from locally sorted sequences—also known as multisequence selection—becomes considerably easier if we allow the precise rank of the output to vary in some range. We then describe how this can be used to construct a bulk priority queue, which we later use to construct an algorithm for weighted reservoir sampling. Lastly, we consider finding the globally most frequent objects as well as those whose associated values add up to the highest sums with a sample-based approach.
In the weighted sampling chapter, we begin by giving new construction algorithms for a classical data structure for weighted sampling, alias tables. After presenting the first linear-time construction algorithm with only constant memory overhead, we proceed to parallelise this algorithm for shared memory, obtaining the first parallel construction algorithm for alias tables. We then show how to approach the problem in distributed memory with a two-level algorithm. Next, we present an output-sensitive algorithm for weighted sampling with replacement, meaning that it requires time linear in the number of unique items in the sample. This algorithm works sequentially as well as in shared and distributed memory and is the first such algorithm in all three categories. We subsequently adapt it to weighted sampling without replacement by combining it with an estimator for the number of unique items in a sample with replacement. Poisson sampling, a generalisation of Bernoulli sampling to weighted items, can be reduced to integer sorting, and we show how an existing approach can be parallelised. For sampling from data streams, we adapt a sequential approach and show how it can be parallelised in a mini-batch model using our bulk priority queue introduced in the selection chapter. The chapter is concluded by an extensive evaluation of our alias table construction algorithms, our output-sensitive algorithm for weighted sampling with replacement, and our weighted reservoir sampling algorithm.
To probabilistically verify the correctness of distributed algorithms, we propose checkers for fundamental operations of big data systems. We show that checking numerous operations can be reduced onto two ‘core’ checkers, namely checking aggregations and whether one sequence is a permutation of another. While multiple approaches exist for the latter and can be easily parallelised, our sum aggregation checker is a novel application of the same data structure that underpins counting Bloom filters and count-min sketches. We implemented both checkers in Thrill, a big data framework. Experiments with deliberately introduced errors confirm the detection accuracy predicted by theory, even when using real-world hash functions with non-ideal properties. Scaling experiments on a supercomputer show that our checkers have very little runtime overhead, in the area of $2\,\%$ for near-certainty in the correctness of the result.
