Pre-processing of graphs

Abstract

Graphs are free of structure; it is simply a set of objects that are related through edges. This makes the graph a versatile format that can be used to model everything from social networks to disease spread and more. Modeling graphs that are based on real world data requires much storage and processing power, resulting in much efforts to process graph efficiently.

This thesis has explored the topic of pre-processing a graph. In particular, we do pre-processing to explore ways of enabling predictable, parallel execution without the overhead of common techniques such as locks. Several techniques for pre-processing and direct execution are implemented and analyzed with respect to both amortized execution time, energy usage and implementation notes. Empirical evaluation is done with scaling up to ten cores. In our results we see that the type of graph and execution methods are important factors to consider in pre-processing.