Eager Maps and Lazy Folds for Graph-Structured Applications

Start Date: February 2009, End Date: January 2011.

We investigate linguistic extensions to map/reduce abstractions for programming large-scale distributed systems, with special focus on applications that manipulate large, unstructured graphs. We target real-world graph analysis tasks found in comparative analysis of biological networks as an important case study.

We address the following specific questions: (i) how can highly unstructured graph-based formalisms be cast in the map/reduce framework? (ii) how effectively can these specifications leverage existing map/reduce infrastructure? (iii) how can these abstractions and their execution environments be enhanced to provide the semantic expressiveness necessary for programmability and scalable performance? (iv) how can these analysis tasks be integrated into comprehensive scientific resources usable by the wider applications community? Answers to these questions entail exploration of linguistic extensions to existing map/reduce abstractions, defining new implementations on wide-area multicore/SMP platforms, and crafting an expressive graph analysis toolkit suitable for realistic deployment in important domains such as systems biology.

Our results advance the state-of-the-art in analysis of large sparse unstructured graphs and directly impact a broad class of scientific applications. Beyond specific target applications in biology, graph-based formalisms find direct applications in social sciences (social networks), recommender systems, and commerce (networks of transactions).