云计算环境下基于BSP模型的大规模图数据查询处理技术

With the rapid growth of the emerging applications like social network analysis, semantic Web analysis, bio-information network analysis, it is urgently required to support high performance query processing ability for large scale graphs with more than billion nodes or edges, which becomes the R & D hot topic in the fields of massive data management and high performance computing. According to the features of clouding computing, this proposal first analyzes the problems of Map-Reduce framework based graph data processing techniques and the shortcomings of existing BSP based graph data processing systems, then proposes the research plan on novel query processing techniques on large scale graph data, including data partitioning and encoding, data storage and indexing, query processing and query optimization, and execution guarantee on clouds. Finally, a large scale graph query processing engine prototype system on cloud computing environments will be implemented. This study is very significant theoretically and practically to develop and apply new data management theory and techniques, to promote cloud technolgoy and applications, and to develop new type of database industry of China.

随着社交网络分析、语义Web分析、生物信息网络分析等新兴应用的快速增长，对亿万个顶点(边)以上大规模图的高效处理能力的需求愈加迫切，是当前海量数据管理和高性能计算领域的研究和开发热点。本申请结合云计算的特点，分析了基于MapReduce框架处理图数据存在的问题以及现有BSP图处理系统的局限，针对新的大规模图数据查询处理技术进行深入研究，计划在数据划分和编码技术、存储和索引技术、查询处理技术和查询优化策略，以及云执行保障机制等方面提出新的解决方案，并实现一个支持大规模图数据处理应用的云查询处理引擎系统原型。该研究对于开发和应用新型的数据管理理论和技术，推动云计算技术与应用，发展我国的新型数据库产业，将具有重要的理论意义和实际价值。

本项目结合云计算的特点，分析了基于MapReduce框架处理图数据存在的问题以及现有BSP图处理系统的局限，针对基于BSP模型的大规模图数据查询处理技术进行深入研究，在数据划分和编码技术、存储和索引技术、查询处理技术和查询优化策略，以及云执行保障机制等方面提出了一系列创新的高效解决方案，并实现了一个支持大规模图数据处理应用的开源的云查询处理引擎系统HybridGraph，在高水平期刊和会议上发表了论文30多篇，其中IEEE TPDS、TKDE、SIGMOD等CCF推荐的A类刊物和会议论文4篇， WWWJ、DASFAA等CCF推荐的B类刊物和会议论文5篇，《计算机学报》、《软件学报》等中文一级学报10篇，SCI检索（源）论文7篇。由清华大学出版社出版了中国计算机学会学术著作丛书《大规模图数据的分布式处理》。该研究对于开发和应用新型的数据管理理论和技术，推动云计算技术与应用，发展我国的新型数据库产业，具有重要的理论意义和实际价值。