Titelaufnahme

Das Hauptaugenmerk dieser Arbeit liegt auf der Entwicklung eines fortgeschrittenen Graphdatenbankenkonzepts welches zukünftigen Anforderungen genügt. Im Besonderen müssen zukünftige Graphdatenbanken ihre Fähigkeit zur Datenspeicherung von größeren Datensätzen und zur schnellen Abarbeitung von komplexeren Abfragen verbessern.

Auf dem Weg dieses Ziel zu erreichen sieht diese Arbeit den Memory Wall Effekt, welcher direkt aus der von Neumann Architektur resultiert, als Haupthindernis. Zur Lösung dieses Problems führt diese Arbeit den Spatially Aware Graph Store als neues Konzept ein. Dieser baut nicht auf einer von Neumann sondern auf einer Spatial Computer (dt. Räumlicher Rechner) Architektur auf. Da ein Spatial Computer aus Millionen von unabhängigen Verarbeitungseinheiten besteht, welche im ein-, zwei- oder dreidimensional physikalischen Raum angeordnet sind, erbt der Spatially Aware Graph Store diese massiv verteilte Umgebung und ist zudem fähig die räumliche Geometrie zur schnelleren Datenverarbeitung zu nützen. Allerdings wirkt sich in Spatial Computer die Distanz zwischen verbunden Knoten maßgeblich auf die erreichbare Geschwindigkeit der Graphtraversierung aus. Aus diesem Grund müssen diese Distanzen minimiert werden um ein effiziente Abarbeitung von Graphoperationen sicherzustellen.

In dieser Arbeit wird gezeigt, dass dies zum einen durch Erhöhung der Dimensionenanzahl des Spatial Computers und zum anderen durch Optimierungsalgorithmen möglich ist. Im letzteren Fall führt diese Arbeit einige neue Methoden ein. Die Mid-Point Optimierung erzielt zunächst ein grobe Minimierung. Sie ist jedoch ausreichend schnell um auch große Datensätze, wie sie bei realen Anwendungen vorkommen, zu verarbeiten. Um das Ergebnis weiter zu verfeinern wird anschließend die Local Node Optimierung ausgeführt. Schließlich zerlegt die Methode Node Decomposition Knoten mit vielen Kanten, in mehrere kleine Knoten mit weniger Kanten. Auf diese Weise können die Distanzen zwischen verlinkten Knoten, insbesondere in scale-free Datensätzen, zusätzlich minimiert werden.

Die Evaluationsergebnisse von realen Datensätzen zeigen, dass Spatially Aware Graph Stores in Kombination mit Distanzoptimerungsalgorithmen eine solide Basis für effizientere Graphdatenbanken bilden. Insbesondere arbeitet diese neue Art von Graphdatenbank auf massiv verteilte Weise, ist nicht vom Memory Wall Effekt betroffen und nützt die die räumliche Struktur von Spatial Computer zur Effizienzsteigerung.

The main concern of this work is the development of a sophisticated graph store concept to cope with future requirements. In particular, future graph stores need to improve significantly their ability, to store larger datasets and to process more complex queries. This work identifies the memory wall effect as the major obstacle for more efficient graph stores, which results from the underlying von Neumann computing architecture.

To address this issue, we introduce the novel concept of a Spatially Aware Graph Store by implementing a graph store not on top of a von Neumann but on a Spatial Computer architecture. As a spatial computer consists of millions of processing units located in one, two or three dimensional physical space, a Spatially Aware Graph Store inherits its massively distributed environment and is able to exploit spatial geometry for faster processing.

However, in spatial computers the physical distance between linked graph nodes strongly affects graph traversal performance. Consequently, these distances need to be minimized to ensure efficiency. The works shows that this can be achieved in two ways. First, by increasing the dimensionality of the spatial computer and second by applying optimization methods. For the latter, this work introduces several novel algorithms. The Mid-Point Optimization is able to quickly calculate rough optimizations for large real world datasets. In addition, the Local Node Optimization is subsequently applied to refine the result. Finally, the Large Node Decomposition method is presented that splits nodes with many edges into several smaller nodes. In particular, for scale-free this method is required to further reduce distances between linked nodes.

The evaluation results on real word datasets show that Spatially Aware Graph Stores in combination with optimization algorithms provide a sound foundation for more efficient graph stores. In particular, the concept is not vulnerable to the memory wall effect, enables distribution on a massive scale and exploits the spatial geometry to gain more efficiency.