Scalable Data-Parallel graph algorithms from generation to management

Abstract

J. J. Sylvester, in 1878, in an article on chemistry and algebra in Nature, called a mathematical structure to model connections between objects, ?graph?. More than a century later, the versatility of graphs as a data model is demonstrated by the long list of applications in mathematics, science, engineering and the humanities.

Graphs are natural data structures for modern applications. Social network data are typically represented as graphs, semantic web is based on RDF formalism that is a graph model, software models and program dependence in software engineering represented via graphs. In many cases these are very large and dynamic graphs. The convergence of applications managing large graphs and the availability of cheap parallel processing hardware caused a renewed interest in managing very large graphs over parallel systems.

In this dissertation, we design scalable and practical graph algorithms for a selected set of large graph generation and management problems. In particular, we provide parallel solutions for graph generation with both random and real-world graph models. Afterward, we propose techniques for processing large graphs in parallel, specifically for computing the Minimum Spanning Forest and the Shortest Path between vertices.