Gesellschaft für Informatik e.V.

Lecture Notes in Informatics


Datenbanksysteme für Business, Technologie und Web (BTW 2015) P-241, 311-330 (2015).

Gesellschaft für Informatik, Bonn
2015


Copyright © Gesellschaft für Informatik, Bonn

Contents

Hochperformante Analyse von Graph-Datenbanken

Moritz Kaufmann , Tobias Mühlbauer , Manuel Then , Andrey Gubichev , Alfons Kemper and Thomas Neumann

Abstract


Ziel des ACM SIGMOD Programming Contest 2014 war es ein hochperformantes System für die Analyse von großen Graph-Daten zu entwickeln. Insbesondere die unregelmäßigen Speicherzugriffsmuster und Kontrollflussverzweigungen von Graphalgorithmen stellen dabei eine große Herausforderung dar, da diese bisher nicht effizient auf modernden superskalaren Mehrkern-Prozessoren ausgeführt werden können. Um diese Prozessoren optimal auszulasten bedarf es zudem der Nutzung aller parallelen Ausführungseinheiten. In der vorliegenden Arbeit präsentieren wir das Gewinnersystem des Wettbewerbs. Der Erfolg unseres Systems beruht, neben gutem Engineering, auf den folgenden Entwicklungen: (i) Daten-parallelisierte Graph-Breitensuche, welche Cache-Misses effizient amortisiert, (ii) Heuristiken zur Reduzierung des Suchraums bei Top-k-Anfragen, (iii) schnelles parallelisiertes Laden von textuellen Rohdaten, und (iv) feingranulares Task-Scheduling um Mehrkern-Prozessoren optimal auszulasten. Die in dieser Arbeit beschriebenen Neuentwicklungen werden derzeit in unser Hauptspeicher-Datenbanksystem HyPer integriert und lassen sich unserer Einschätzung nach auch in bestehende Graph-Datenbanksysteme integrieren.


Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-635-0


Last changed 30.04.2015 15:16:32