Logo des Repositoriums
 

Efficient Batched Distance and Centrality Computation in Unweighted and Weighted Graphs

Kurzanzeige
dc.contributor.authorThen, Manuel
dc.contributor.authorGünnemann, Stephan
dc.contributor.authorKemper, Alfons
dc.contributor.authorNeumann, Thomas
dc.contributor.editorMitschang, Bernhard
dc.contributor.editorNicklas, Daniela
dc.contributor.editorLeymann, Frank
dc.contributor.editorSchöning, Harald
dc.contributor.editorHerschel, Melanie
dc.contributor.editorTeubner, Jens
dc.contributor.editorHärder, Theo
dc.contributor.editorKopp, Oliver
dc.contributor.editorWieland, Matthias
dc.date.accessioned2017-06-20T20:24:28Z
dc.date.available2017-06-20T20:24:28Z
dc.date.issued2017
dc.description.abstractDistance and centrality computations are important building blocks for modern graph databases as well as for dedicated graph analytics systems. Two commonly used centrality metrics are the compute-intense closeness and betweenness centralities, which require numerous expensive shortest distance calculations. We propose batched algorithm execution to run multiple distance and centrality computations at the same time and let them share common graph and data accesses. Batched execution amortizes the high cost of random memory accesses and presents new vectorization potential on modern CPUs and compute accelerators. We show how batched algorithm execution can be leveraged to significantly improve the performance of distance, closeness, and betweenness centrality calculations on unweighted and weighted graphs. Our evaluation demonstrates that batched execution can improve the runtime of these common metrics by over an order of magnitude.en
dc.identifier.isbn978-3-88579-659-6
dc.identifier.pissn1617-5468
dc.language.isoen
dc.publisherGesellschaft für Informatik, Bonn
dc.relation.ispartofDatenbanksysteme für Business, Technologie und Web (BTW 2017)
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume P-265
dc.subjectGraph Databases
dc.subjectGraph Analytics
dc.subjectCloseness Centrality
dc.subjectBetweenness Centrality
dc.titleEfficient Batched Distance and Centrality Computation in Unweighted and Weighted Graphsen
dc.typeText/Conference Paper
gi.citation.endPage266
gi.citation.startPage247
gi.conference.date6.-10. März 2017
gi.conference.locationStuttgart
gi.conference.sessiontitleData Analytics

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild
Name:
paper17.pdf
Größe:
557.54 KB
Format:
Adobe Portable Document Format
Herunterladen

Sammlungen

P265 - BTW2017 - Datenbanksysteme für Business, Technologie und Web