Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Query-Driven Index Partitioning for TripleRush
Organization Unit
Authors
  • Christian Tschanz
Supervisors
  • Philip Stutz
Language
  • English
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Number of Pages 12
Date 2014
Abstract Text TripleRush is a distributed RDF triple store that can be queried with a subset of SPARQL. The index structure of TripleRush is represented as a graph. Executing a query on TripleRush will send messages along the edges in the index graph. This leads to messages being sent between different server nodes as the index graph vertices are distributed over multiple servers. The hypothesis is, that a big part of the query execution time is due to network latency. Reducing the amount of messages traversing the network during query execution would result in improved execution times. The goal of this thesis is to improve the query execution times of a specific set of queries by analyzing how TripleRush executes them and devising optimization strategies to reduce the inter-node network traffic. These optimizations are based on query execution logs of these queries. These logs represent a sub-graph, the query graph, of the index structure. The discussed approach uses the query graph to re-distribute the relevant parts of the index structure. This optimizes the index graph in such a way that the studied set of queries will run faster due to the optimized vertex placement. The aim is to re-partition parts of the index structure to reduce inter-node edges while maintaining an even distribution for load balancing. Two approaches are proposed to re-partition and transform the query graph to produce an optimized distribution of TripleRush index vertices. The resulting datasets can be re-introduced into TripleRush with minimal modifications to TripleRush. It has been found that one of the approaches shows promise to significantly improve query execution times for the studied set of queries, while maintaining the distributed load balancing.
Zusammenfassung TripleRush ist eine verteilte RDF Triple Datenbank, welche ein Subset von SPARQL Anfragen unterstützt. Die Index Struktur von TripleRush ist ein Graph. Bei der Ausführung einer Anfrage werden Nachrichten entlang der Kanten im Indexgraphen verschickt. Da die Indexgraph Knoten über mehrere Server verteilt sind, führt eine Ausführung einer Anfrage dazu, dass Nachrichten über das Netzwerk verschickt werden. Die Hypothese ist, dass ein Grossteil der Anfragen Ausführung auf die Netzwerklatenz zurück geführt werden kann. Reduziert man die Anzahl der Nachrichten welche über das Netzwerk verschickt werden, kann man die Ausführzeiten reduzieren. Das Ziel dieser Arbeit ist es zu analysieren wie TripleRush eine Auswahl an Anfragen ausführt und basierend darauf Optimierungsstrategien zu entwickeln um den inter-Server Netzwerk Verkehr für diese Anfragen zu reduzieren. Dafür wird das Ausführen der Anfragen aufgezeichnet. Diese Aufzeichnungen repräsentieren einen sub-Graphen (Querygraph) der ganzen Indexstruktur. Die besprochenen Optimierungstechniken benützen den Querygraphen um die relevanten teile des Indexgraphen neu zu verteilen. Dies optimiert den Indexgraphen so, dass die untersuchten Anfragen schneller ausgeführt werden können, da die benötigten Index Knoten besser verteilt sind. Das Ziel ist es Teile des Indexgraphen so neu zu verteilen, dass die Anzahl von inter-Server Nachrichten minimiert wird und gleichzeitig die Verteilung der Knoten möglichst gleichmässig zu halten, damit die Leistungsabstimmung aufrecht erhalten werden kann. Zwei Strategien um den Querygraphen neu zu partitionieren werden vorgeschlagen. Die resultierenden Datenstrukturen können wieder in TripleRush eingespeist werden, ohne grössere Modifikationen an TripleRush vornehmen zu müssen. Eine der Strategien hat sich als vorteilshaft erwiesen. Es war damit möglich die Ausführungszeiten der Anfragen drastisch zu reduzieren und gleichzeitig die Verteilung der Index Knoten relativ konstant zu halten.
PDF File Download
Export BibTeX