Eager Maps and Lazy Folds for Graph-Structured Applications

这个项目正在研究语言扩展，以映射/减少编程大规模分布式系统的抽象，特别关注操作大型非结构化图形的应用程序。它以生物网络比较分析中的真实世界图分析任务为目标，研究了以下具体问题：(I)高度非结构化的基于图的形式化如何被投射到MAP/REDUE框架中？(2)这些规范能在多大程度上有效地利用现有的地图/减少基础设施？(Iii)如何增强这些抽象及其执行环境，以提供可编程性和可伸缩性能所需的语义表达能力？(4)如何将这些分析任务整合为更广泛的应用界可用的综合科学资源？这些问题的答案包括探索现有MAP/REDUE抽象的语言扩展，在广域多核/SMP平台上定义新的实现，以及制作适合于系统生物学等重要领域的现实部署的富于表现力的图形分析工具包。该项目产生的结果推动了大型稀疏非结构化图形分析的最先进水平，并直接影响了非常广泛的科学应用类别。除了生物学中的特定目标应用之外，基于图的形式主义还可以直接应用于社会科学(社交网络)、推荐系统和商业(交易网络)。

This project is investigating linguistic extensions to map/reduce abstractions for programming large-scale distributed systems, with special focus on applications that manipulate large, unstructured graphs. It targets real-world graph analysis tasks found in comparative analysis of biological networks as an important case study.The project is investigating 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 entails exploring 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.Results that arise from this project advance the state-of-the-art in analysis of large sparse unstructured graphs and directly impact a very 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).