Location: Second Floor Conference Room (2018)

Date: 03/27/2015

Time: 2:30 PM

Speaker 1: S. M. Arifuzzaman

Title: Fast Parallel Conversion of Edge List to Adjacency List for Large-Scale Graphs

Abstract: In the era of Big-data, we are deluged with massive graph  data emerged from numerous social and scientific applications. In most cases, graph data are generated as lists of edges (edge list), where an edge denotes a link between a pair of entities. However, most of the graph algorithms work efficiently when information of the adjacent nodes (adjacency list) for each node are readily available. Although the conversion from edge list to adjacency list can be trivially done on the fly for small graphs, such conversion becomes challenging for the emerging large-scale graphs consisting billions of nodes and edges. These graphs do not fit into the main memory of a single computing machine and thus require distributed-memory parallel or external-memory algorithms. In this talk, I'll present efficient MPI-based distributed memory parallel algorithms for converting edge lists to adjacency lists. This work demonstrates how a simple problem turns into a challenging one when we are dealing with Big-data.