自适应云端的大规模导出子图提取算法

Large Scale Induced Subgraphs Mining Algorithm on Self Adaptive Cloud

针对现有云计算平台资源随机调配与传统导出子图挖掘效率较低等问题,进一步提升云计算平台中资源整合利用效率与大规模导出子图挖掘效率,提出了一种自适应云端的大规模导出子图提取算法,以解决资源优化利用与海量图挖掘等问题。首先介绍了云计算概念与导出子图挖掘相关概念以及问题描述;接着根据MapReduce并行处理模型设计了一种自适应任务动态分配算法SAC_TA(Self Adaptive Cloud Dynamic Allocation),它根据计算任务自适用分配系统资源以达到成本消耗的最优;并设计出自适应云端框架,然后基于自适应云端提出了大规模导出子图挖掘算法SFGFF(SAC_TA、Find_VE、G_F1、FindPartFG、FindAllFG),它共分为4个阶段的挖掘,将所有算法应用到自适应云端中可构成整个导出子图挖掘体系;最后在人工模拟数据与真实环境数据下进行了试验,结果表明,自适应云端运行良好,算法有效可行,具有较高的加速比与运行效率,能有效满足大规模频繁导出子图挖掘的需求。

Aiming at the current puzzles of random resource allocation of cloud computing platform and lower mining efficiency of traditional induced subgraph,promoting the efficiency of resource integration and using of cloud computing platform and large-scale induced subgraph mining,the paper put forward an algorithm of large-scale induced subgraph extraction for self-adaption cloud to solve the problems of resource optimal utilization and massive graph mining.The paper firstly introduced the relevant concepts and problem description of cloud computing and induced subgraph mining,then designed an algorithm SAC_TA of self-adaption task dynamic allocation according to MapReduce parallel processing model,which can comput task self-adaption allocation system resources to reach the optimum of cost wasting,meanwhile designed the self-adaption cloud framework.On the basis of the framework,the paper put forward the massive induced subgraph mining algorithm SFGFF,which includs four stages of mining.And while applying all the algorithms to self-adaption cloud,the whole induced subgraph mining system can be constructed.The experimental result of manual simulation data and real environment data shows that the self-adaption cloud runs well and the algorithms are efficient and feasible,and have higher speed-up ratio and operating efficiency to satisfy the demand of massive frequent induced subgraph mining.