@inproceedings{8129294a48c5454e82e3b8f8105a8812,
title = "Efficient batched distance and centrality computation in unweighted and weighted graphs",
abstract = "Distance 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.",
keywords = "Betweenness centrality, Closeness centrality, Graph analytics, Graph databases",
author = "Manuel Then and Stephan G{\"u}nnemann and Alfons Kemper and Thomas Neumann",
note = "Publisher Copyright: {\textcopyright} 2017 Gesellschaft fur Informatik (GI). All rights reserved.; Datenbanksysteme fur Business, Technologie und Web, BTW 2017, 17. Fachtagung des GI-Fachbereichs {"}Datenbanken und Informationssysteme�, DBIS - Database Systems for Business, Technology and Web, BTW 2017, 17th Symposium of the GI Department {"}Databases and Information Systems{"}, DBIS ; Conference date: 06-03-2017 Through 10-03-2017",
year = "2017",
language = "English",
series = "Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI)",
publisher = "Gesellschaft fur Informatik (GI)",
pages = "247--266",
editor = "Bernhard Mitschang and Daniela Nicklas and Frank Leymann and Harald Schoning and Melanie Herschel and Jens Teubner and Theo Harder",
booktitle = "Datenbanksysteme fur Business, Technologie und Web, BTW 2017 - 17. Fachtagung des GI-Fachbereichs {"}Datenbanken und Informationssysteme�, DBIS 2017, Proceedings",
}