云环境下大规模动态图数据查询处理与优化技术研究

With the rapid development of the Internet and Cloud Computing techniques, the emerging applications like social network analysis, semantic Web analysis and bioinfornatics network analysis grow sharply, leading to the urgent require of processing capalility on large scale graphs. However, the graph data is no longer a static structure and has highly dynamic nature of the vertex attribute, edge attribute and topological structure, because the big data has the characteristics, such as timeliness, sudden and sociality. So, the traditional large scale graph data processing techniques cannot effectively deal with the large dynamic graph data. The efficient processing of the large dynamic graph data has become a new research hotspot and difficulty in areas of massive data management and high-performance computing. Therefore, according to the features of Cloud Computing and the large dynamic graph data management problems, this project proposes the new research plan on Large dynamic graph data modeling and storage techniques, distributed indexing techniques, distributed query processing and optimization techniques on Cloud Computing environments. Finally, a large dynamic graph data management prototype system will be designed and implemented. This study work of the project has the very significant theoretically and practically value to provide strong theoretical support and good solutions for the data management of large dynamic graph.

伴随着互联网和云计算技术的飞速发展，社交网络分析、语义Web分析、生物信息网络分析等多种新型应用的需求快速增长，对大规模图数据处理的要求也更加迫切。然而，由于大数据具有时效性、突发性和社会性等特点，直接导致图不再是静态结构，而在顶点属性、边属性以及拓扑结构上具有高度的动态性，使得传统的大规模图数据查询处理技术无法有效地处理大规模动态图数据。针对大规模动态图数据的高效处理已经成为海量数据管理和高性能计算等领域新的研究热点和难点。因此，本项目围绕大规模动态图数据管理所面临的问题，结合云计算技术的特点，针对云环境下大规模动态图数据的建模与存储技术、分布式索引技术和分布式查询处理与优化技术提出新的解决方案，并设计实现一个支持大规模动态图数据管理的原型系统。该项目的研究工作将为大规模动态图数据管理的应用提供有力的理论支持和良好的解决方案，具有深远的理论研究意义和重要的实际应用价值。

图作为重要的数据结构而被广泛用于描述生物信息、web语义分析、社交网络分析等领域的复杂网络关系。随着信息技术、互联网和云计算技术等的深度发展，数据规模极速增长，对大规模图数据处理的需求也愈加迫切。此外，大数据具有的时效性、突发性和社会性等特点导致大规模图数据在顶点属性、边属性以及拓扑结构上具有高度的动态性，传统的静态大规模图数据查询处理技术已无法有效地处理当前大规模动态图数据，如何高效处理大规模动态图数据已成为海量数据管理和高性能计算等领域新的研究热点和难点。针对于此，本课题围绕大规模动态图数据管理所面临的问题，结合云计算技术的特点，对云环境下大规模动态图数据查询处理与优化技术进行深入研究，其中针对大规模动态图数据的建模与存储技术，提出基于B+树的大规模图分割结果标记存储方法、双压缩图存储方法、基于范德蒙码的HDFS优化存储方法等存储方法；针对分布式索引技术，提出图拓扑结构特性索引、频繁结构映射和标签值聚合的二级索引、折叠树编码索引等多种索引方法；针对分布式查询处理与优化技术，提出基于改进哈夫曼编码的可达查询处理方法、标签约束的频繁子图Top-k查询方法、大规模动态标签图上的动态Top-k兴趣子图查询方法、中心核稠密子图查询方法等若干满足不同需求的查询优化方法。同时本课题充分考虑大规模动态图数据的特点，将MapReduce框架和BSP 处理模型进行有效的结合和嵌套，设计并实现了一种“MapReduce+BSP”模式的专门用于大规模动态图处理算法的轻量级框架平台。大量实验表明，该课题提出的存储、索引及查询方法具有良好的有效性和可行性。该课题的研究工作将为大规模动态图数据管理的应用提供有力的理论支持和良好的解决方案，具有深远的理论研究意义和重要的实际应用价值。