Go to page
 

Bibliographic Metadata

Title
DynamoGraph : large-scale temporal graph processing and its application scenarios / eingereicht von Matthias Steinbauer
Additional Titles
DynamoGraph: Verteilte Verarbeitung großer temporaler Graphen und Anwendungsszenarien
AuthorSteinbauer, Matthias
CensorAnderst-Kotsis, Gabriele ; Spirakis, Paul
PublishedLinz, December 2016
DescriptionXIV, 189 Blätter : Illustrationen
Institutional NoteUniversität Linz, Dissertation, 2016
Annotation
Zusammenfassung in deutscher Sprache
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
https://steinbauer.org/dynamograph/
LanguageEnglish
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)verteiltes Rechnen / große Graphen / temporale Graphen / Netzwerke
Keywords (EN)distributed computing / large graphs / temporal graphs / networks
Keywords (GND)Verteiltes System / Berechnung / Graph / Temporalität / Netzwerk
URNurn:nbn:at:at-ubl:1-13550 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
DynamoGraph [6.3 mb]
Links
Reference
Classification
Abstract (German)

When computers (people) are networked, their power multiplies geometrically. Not only can people share all that information inside their machines, but they can reach out and instantly tap the power of other machines (people), essentially making the entire network their computer. - Scott McNeely Scott McNeely's Vision ist Realität geworden, wir befinden uns in der Era einer vernetzten Welt, in der Menschen, Computer und auch ganz einfach Dinge im Internet of Things miteinander vernetzt sind. Obwohl Netzwerk-Datenstrukturen (Graphen) ein sehr genau untersuchtes Forschungsfeld darstellen, stellt sich heraus, dass in vielen Anwendungen gerade die Änderung in der Netzwerkstruktur von besonderer Bedeutung ist z.B. Personen die einer Gruppe beitreten. Obwohl die formalen Konzepte für veränderliche Graphen (dynamischer Graph) und auch für Graphen die diese zeitliche Änderung aufzeichnen (temporaler Graph) schon lange existieren gibt es bisher vergleichsweise wenige Studien in der angewandten Informatik. Ein Grund dafür ist sicherlich, dass die angesprochenen Anwendungsszenarien nicht nur nach temporalen Graphen verlangen, sondern üblicherweise auch aus sehr großen Datensätzen bestehen, so dass sehr große temporale Graphen verarbeitet werden müssen. Um Datenverarbeitung auf immer weiterwachsende Datenmengen skalieren zu können ist das sogenannte horizontale Skalieren das aktuell bevorzugte Modell. Mehrere Rechner, meist auf Basis von Cloud Infrastruktur, werden im Verbund verwendet. In dieser Arbeit wird DynamoGraph, ein Softwaresystem für verteiltes Rechnen auf großen temporalen Graphen, als Lösungsansatz vorgestellt. Mit Hilfe von DynamoGraph ist es möglich temporale Graphdaten auf Basis einer temporalen Indexdatenstrukur in einem Rechnerverbund zu verteilen. Die Datenstruktur funktioniert analog zu existierend Indexdatenstrukturen speichert aber Metadaten zur Dimension Zeit, dies kann später wiederum in der, auch in dieser Arbeit diskutierten Pregel Implementierung für temporale Graphen, verwendet werden zum Beispiel um Daten aus bestimmten Zeitfenstern zu verarbeitet. Der Einsatz von DynamoGraph in praktischen Fallbeispielen zeigt, dass der Ansatz von Softwareentwicklern in der Praxis, mit vergleichsweise flacher Lernkurve, eingesetzt werden kann. Weiters wird gezeigt, dass die Methode aus dem verteilten Rechnen, Skalierbarkeit der Rechner-Ressourcen aber auch des Datensatzes erlaubt. Performance Tests zeigen, dass die Zugewinne durch das verteilte Rechnen so hoch sind, dass es in der praktischen Anwendung unumgänglich ist.

Abstract (English)

When computers (people) are networked, their power multiplies geometrically. Not only can people share all that information inside their machines, but they can reach out and instantly tap the power of other machines (people), essentially making the entire network their computer. - Scott McNeely Scott McNeely's vision became reality; we have now implemented a networked world. Machines are networked, humans form networks and we are at the brink of all and everything in our lives being connected in the Internet of things. While network structures (graphs) are very well studied, in this thesis it is argued that for many problems not only structure is of interest but the change in this structure might be of even higher relevance e.g. the events of individuals joining or leaving groups in a social network. It is discussed that, although the formal concepts of changing graphs (dynamic graph) and graphs which track all changes made to them over time (temporal graphs) exist for a long time, up to now comparatively little use of these concepts is made in applied computing. One of the reasons for this is that the application areas often are of very large size such that actually large-scale temporal graphs are the data structure of concern. For large datasets horizontally scaled computing systems based on cloud computing infrastructure, are the prevalent approach to gain speedup and to solve problems in feasible time. This thesis discusses a distributed computing framework called DynamoGraph which allows to partition large-scale temporal graph data over multiple compute nodes. Vertices are at the core of the used data model and are implemented using temporal maps, a map data-structure that tracks temporal meta-information of the stored data. This mechanism is exploited in an extension of the Pregel graph processing paradigm which makes it applicable for temporal graphs. The work shows the practical feasibility with case-studies and the general scalability (compute resources and data size) of the approach. The experimental performance evaluation shows that the distributed computing approach provides significant gains and thus is inevitable in real-world set- tings.

Stats
The PDF-Document has been downloaded 41 times.