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

Large Scale Induced Subgraphs Mining Algorithm on Self Adaptive Cloud

作　　者：郭鑫[1] 董坚峰[2] 周清平[1] 

机构地区：[1]吉首大学软件服务外包学院,张家界427000 [2]武汉大学信息资源研究中心,武汉430072

出　　处：《计算机科学》2014年第6期155-160,198,共7页Computer Science

基　　金：湖南省工业支撑计划重点项目(2012GK2006);湖南省教育厅科学研究项目(12C0291;11C1051);生态旅游湖南省重点实验室开放基金项目(JDSTLY201206);湖南省图书馆学会2013-2014年度重点课题(XHZD1007)资助

摘　　要：针对现有云计算平台资源随机调配与传统导出子图挖掘效率较低等问题,进一步提升云计算平台中资源整合利用效率与大规模导出子图挖掘效率,提出了一种自适应云端的大规模导出子图提取算法,以解决资源优化利用与海量图挖掘等问题。首先介绍了云计算概念与导出子图挖掘相关概念以及问题描述;接着根据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.

关 键 词：大数据 数据挖掘 云计算 导出子图 子图同构 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]