Abstract: The MapReduce programming paradigm is widely used in industry for analyzing large data sets. Often data can be represented as graphs. Many previous graph algorithms for solving graph problems in the MapReduce simply filter edges and solve a smaller version of the problem repeatedly until the entire graph has been analyzed. These algorithms require dense graphs to work efficiently. However, it is not uncommon for large data sets to be sparsely populated. Here algorithms for maximal matching, approximate minimum edge covering, and approximate maximum weighted matching are presented and analyzed for a family of sparse graphs called grid graphs.
Committee Members: Dr. Vinod Variyam (Advisor), Dr. Ashok Samal and Dr. Stephen Scott