Hochperformante Analyse von Graph-Datenbanken
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.
- Citation
- BibTeX
Kaufmann, M., Mühlbauer, T., Then, M., Gubichev, A., Kemper, A. & Neumann, T.,
(2015).
Hochperformante Analyse von Graph-Datenbanken.
In:
Seidl, T., Ritter, N., Schöning, H., Sattler, K.-U., Härder, T., Friedrich, S. & Wingerath, W.
(Hrsg.),
Datenbanksysteme für Business, Technologie und Web (BTW 2015).
Bonn:
Gesellschaft für Informatik e.V..
(S. 311-330).
@inproceedings{mci/Kaufmann2015,
author = {Kaufmann, Moritz AND Mühlbauer, Tobias AND Then, Manuel AND Gubichev, Andrey AND Kemper, Alfons AND Neumann, Thomas},
title = {Hochperformante Analyse von Graph-Datenbanken},
booktitle = {Datenbanksysteme für Business, Technologie und Web (BTW 2015)},
year = {2015},
editor = {Seidl, Thomas AND Ritter, Norbert AND Schöning, Harald AND Sattler, Kai-Uwe AND Härder, Theo AND Friedrich, Steffen AND Wingerath, Wolfram} ,
pages = { 311-330 },
publisher = {Gesellschaft für Informatik e.V.},
address = {Bonn}
}
author = {Kaufmann, Moritz AND Mühlbauer, Tobias AND Then, Manuel AND Gubichev, Andrey AND Kemper, Alfons AND Neumann, Thomas},
title = {Hochperformante Analyse von Graph-Datenbanken},
booktitle = {Datenbanksysteme für Business, Technologie und Web (BTW 2015)},
year = {2015},
editor = {Seidl, Thomas AND Ritter, Norbert AND Schöning, Harald AND Sattler, Kai-Uwe AND Härder, Theo AND Friedrich, Steffen AND Wingerath, Wolfram} ,
pages = { 311-330 },
publisher = {Gesellschaft für Informatik e.V.},
address = {Bonn}
}
Haben Sie fehlerhafte Angaben entdeckt? Sagen Sie uns Bescheid: Send Feedback
More Info
ISBN: 978-3-88579-635-0
ISSN: 1617-5468
xmlui.MetaDataDisplay.field.date: 2015
Language:
(de)

Content Type: Text/Conference Paper