Approximating distributed graph algorithms

Abstract

The interest in the ability of processing data that has an underlying graph structure is grown in the recent past. This has led to the development of many distributed graph processing systems. But these existing graph processing systems take several minutes or even hours to execute popular graph algorithms. The amount of data is also growing fast, for example, the world wide web or social graphs. This leads to the question: do we always need to know the exact answer for a large graph? In other fields like big data analytics, approximation gained interest in recent time, the user can decide about the accuracy of the result and if the user accepts a less accurate result the calculations could be speed up. Also, for distributed event based systems, such as publish/subscribe, and stream processing systems approximation techniques exists. For distributed graph processing exists only a few approaches that provide approximation techniques. Most of these approaches concentrate on sparsification of the graph or approximation of the vertex function itself. But the bottleneck in distributed graph processing arises mainly from the message passing between vertices. This thesis, investigates message dropping for the Page Rank algorithm. Two ways of message dropping are investigated, individual dropping of messages based on message properties and dropping all messages from selected edges (edge sampling). The dropping aims to reduce the runtime, while minimize the error. Both approaches are tested with different properties. A detailed analysis of the results of both approaches and the different properties is presented. The evaluation is done on three real world graphs. The error metrics used for the evaluation are also described in this thesis.

Das Interesse, Algorithmen auf Graphen ausführen zu können, hat zuletzt stark zugenommen. Dies hat zur Entwicklung von verteilten Graph-Verarbeitungssystemen geführt. Aber diese Systeme brauchen zur Berechnung von gängigen Graph-Algorithmen mehrere Minuten oder sogar Stunden. Auch die Menge an Daten wächst ständig. Beispiele hierfür sind das World Wide Web oder die Graphen sozialer Netzwerke. Dies alles führt zu der Frage, ob immer das exakte Ergebnis eines Algorithmus nötig ist. In anderen Bereichen, wie Big-Data-Anwendungen, haben Approximationen zuletzt stark an Aufmerksamkeit gewonnen. Der Anwender kann über die Genauigkeit des Ergebnisses entscheiden, und wenn er ein weniger genaues Ergebnis akzeptiert, können die Berechnungen beschleunigt werden. Auch in Anwendungen zur verteilten Verarbeitung von Ereignissen und zur Verarbeitung von Datenströmen (Streams) existieren Techniken zur Approximierung. Für verteilte Graph-Verarbeitungssysteme existieren erst einige wenige Ansätze mit Techniken zur Approximierung. Die meisten dieser Ansätze behandeln die Ausdünnung des Graphen oder die Vereinfachung der Funktion auf dem Knoten selbst. Doch der limitierende Faktor bei der verteilten Verarbeitung von Graphen ist hauptsächlich der Nachrichtenaustausch zwischen den Knoten. Diese Arbeit untersucht das Löschen von Nachrichten am PageRank-Algorithmus. Zwei Arten von Nachrichtenlöschungen wurden untersucht. Das Löschen von Nachrichten auf der Basis von Nachrichteneigenschaften und das Löschen aller Nachrichten über eine Kante (das Löschen der Kante). Durch das Löschen soll die Laufzeit der Programme reduziert werden, wobei der Fehler so klein wie möglich bleiben soll. Beide Ansätze wurden mit unterschiedlichen Eigenschaften getestet. Eine detaillierte Analyse der Ergebnisse von beiden Ansätzen und der unterschiedlichen Eigenschaften erfolgte auf drei reellen Graphen. Auch die Metriken zur Bestimmung der Fehlers werden in der Arbeit beschrieben.