基于分布式计算框架的大图数据描述性查询关键技术研究

Big graphs and their applications raise enormous challenges and opportunities to database researchers. It is a practical solution to exploit the existing MapReduce framework in managing big graphs to achieve a high scalability. In order to improve the performance of graph query in the MapReduce framework, and lessen the burdens of end uses in coding and debugging distributed programs, this project plans to study the key techniques of declarative query on big graphs using MapReduce framework. Specifically, this project will design a declarative graph query language based on recursive Datalog to ease the burdens of end users, propose a method to construct query evaluation plans using MapReduce, and devise query optimization and dynamic binding strategies based on a cost model. In addition, this project will study the extensions to the underlying MapReduce framework, including the global caching mechanism for iterative invariance in MapReduce job, and adaptive partitioning strategy for load balance in the reduce side. In addition, this project will build a prototype for the declarative graph query language based on Hadoop system, which is an open source implementation of MapReduce framework.

大图数据及其上应用为数据管理技术带来了巨大的挑战和机遇。利用现有相对成熟的MapReduce分布式计算框架管理大图数据是现实可行的技术方案。本课题针对现有框架下大图数据查询性能难以满足应用需求、用户编写图数据处理脚本繁琐低效等问题，围绕MapReduce框架下大图数据描述性查询，从理论方法与关键技术、原型系统两个层面展开研究工作。在理论方法与关键技术层面，本课题拟提出基于递归Datalog的描述性图查询语言，简化最终用户编写图操作脚本的代价；拟提出基于MapReduce框架的描述性图查询执行计划的构建方法，设计基于代价模型的优化和动态绑定策略；拟提出MapReduce框架中面向循环不变量的缓存策略，设计面向负载平衡的任务自适应分配机制，扩展分布式计算框架对大图数据管理的支持。在原型系统层面，本课题基于分布式计算框架MapReduce的开源系统Hadoop研制大图数据描述性查询的原型系统。

大图数据及其上应用为数据管理技术带来了巨大的挑战和机遇。利用现有相对成熟的分布式计算框架管理大图数据是现实可行的技术方案。本课题针对现有框架下大图数据查询性能难以满足应用需求、用户编写图数据处理脚本繁琐低效等问题，围绕分布式框架下大图数据查询和分析，从理论方法与关键技术、原型系统两个层面展开研究工作。在理论方法与关键技术层面，本课题提出了基于递归Datalog的描述性图查询语言，简化最终用户编写图操作脚本的代价；提出了以节点为中心计算模型下的图模式匹配方法，提高模式查询的扩展性，保证查询结果在动态大图之上的有效性，并扩展支持多查询优化；设计了分布式框架的资源优化框架MocGraph，减少框架运行过程中的资源消耗；设计了支持同步和异步操作的分布式大图处理框架GiraphAsync，在统一框架中支持同步图分析和异步图查询。基于上述研究进展，发表或者录用论文12篇，其中CCF A类论文8篇，包括VLDB、ICDE、AAAI、TKDE、VLDBJ等；申请专利1项；研究成果在阿里巴巴公司得到应用，利用千台分布式计算节点分析大图数据支持商品图推荐，取得良好应用效果。