2016-01-27 Maximum Flow implementation on Spark GraphX

Maximum Flow algorithm implementation on Spark GraphX - Abstract

Link to slideshow: PDF Slideshow

GraphX is an API for graph computation built upon Apache Spark, a fast and generalized engine for large-scale data processing in the cloud. While the popularity of Spark and GraphX is growing, the relatively young technology has yet to explore the breadth of graph problems that exist in the field. In order to examine and gain insights into the capabilities of GraphX, this thesis approaches the framework with the intention of implementing a solution to the Maximum Flow Problem, a complex graph problem without a trivial distributed approach. Specifically, the implementation is to be based on the serial Push-Relabel algorithm. An original MapReduce-based approach to the problem is presented, as well as an implementation of the approach in GraphX. In addition to the implementation, experimentation and deployment to an Amazon EC2 cluster allowed observations on caching and checkpointing intervals to be made. 

Ryan Langewisch - Bio

Ryan Langewisch graduated from Colorado School of Mines with his BS in Computer Science in December of 2014, and his MS in Computer Science in December of 2015. For his Master's work, Ryan gained exposure to algorithms in the context of distributed computing, ultimately leading to his thesis, "A Performance Study of an Implementation of the Push-Relabel Maximum Flow Algorithm in Apache Spark's GraphX." In 2016, Ryan will join ReadyTalk in Denver, CO as a software engineer.