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
Archived Story: This article is part of our newsletter archives. It has
been preserved for reference, but the information may no longer be current.