大规模图处理研究

《大规模图处理研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大规模图处理研究张慧玲*，宁立*，孟金涛*，魏彦杰，冯圣中（中国科学院深圳先进技术研究院高性能计算研究中心，广东深圳市南山区西丽学苑大道1068号518055）摘要:大数据研究领域的许多问题可以转换为图的问题。本文中将具体阐述鲲鹏大数据系统计算引擎研究中有关大规模图处理的研究以及应用。关键词:DeBrujin图，图模式匹配,稀疏数据存储结构,基因拼接OnLargeScaleGraphProcessingZhangHL;NingL；MengJT;WEIYJ;FENGSZ（CenterforHighP

2、erformanceComputing,ShenzhenInstitutesofAdvancedTechnology,1068XueyuanAvenue,ShenzhenUniversityTown,Shenzhen,China518055）【Abstract】Graphtheorycanbeusedtotacklemanyproblemsforbigdataresearch.ThispaperpresentsseveralimportantprogressesofKunPengBigDataSy

3、stemongraphprocessing.【Keywords】DeBrujinGraph,GraphPatternMatching,SparseDataRepresentation,GeneAssembly正文（层次编号范例如下）1背景介绍数据的爆炸性增长是信息时代最典型的特征。IDC的研究报告指出，2011年，全球已有1.8ZB（即1.8万亿GB）数据创建产生。这相当于每位美国人每分钟写3条Tweet，而且还是不停地写2.7万年。而全球90%的数据都是在过去两年中生成的，其中2011到2012

4、年全球所创建的数据内容增长了48%。Google数据中心的服务器规模以达数百万台，每天处理的数据量超过100PB。如何从海量数据中分析和挖掘潜在的价值是大数据研究的重点。众多领域的可用大数据在生物信息学、社会科学、连接分析、引证分析以及协同网络等许多应用中都以图的形式表现。图由节点和连接节点的边构成，边用来描述节点之间的关系；因此图可以用来研究生物、物理、社会、信息系统内的各种关系和动态过程。图的挖掘和分析，比如子图匹配查询，对于大数据研究中的数据价值发现意义重大。本文从三个方面分别介绍鲲鹏大数据

5、系统中大规模图研究的进展：高效子图匹配查询，面向图问题的稀疏数据存储结构，异构图计算模型及其应用。2高效子图匹配查询算法图模式匹配(GraphPatternMatching,GPM)本来是指子图同构问题，即决定一个较小的图模式是否被另一个图包含[1][2]。近年来，基于大型独立图处理的应用在不断增加，从已有的大型图中挖掘模式并与给定的查询图模式相匹配已经成为非常重要的一个课题。给定一个查询图，GPM通常会要求返回所有的解。但对于一个大型图，其查询图解的数量将会十分庞大。如果将所有解都返回，不仅会给

6、用户处理带来许多麻烦，而且其计算难度也会令人望而生畏。与其他工作不同[3-5]，我们研发的高效子图匹配算法创新之处在于：对大型独立数据图，我们仅考虑查询图的k个最优解，即top-k图模式匹配问题(kGPM),该方法可以高效寻找带环查询图的top-k解[6]。采用已有的子图匹配算法找出全部匹配解，然后通过排序取得top-k结果会十分耗时。我们的解决方法是采用飞式排序方法处理该问题。对于一个给定的查询图Q,我们选定一个或多个基于Q的生成树，每一棵生成树都根据评分函数的打分，非升序地返回解。因此，每棵生

7、成树都对应一个解的排序列表。生成树匹配得到的解与带环图具有相同的顶点，但是会缺失部分边，因此可以搜索缺失的边在数据图是否存在对应的路径。如果存在，则表示生成树的解扩展后成为带环图在数据图中对应的匹配图；若不存在，则不可以扩展。既然构建排序列表可以加快kGPM的匹配速度，那么我们是否应该构建尽可能多的生成树呢？答案是否定的。因为构建多个排序列表的花费十分巨大。因此选择生成树集合从而使解决kGPM所需的花费最小就显得十分必要。我们的解决方案是采用基于成本的优化方法去寻找kGPM的最优查询方法。我们首先

8、使用多个排序列表去应答一个给定的查询图Q,以实现多维表征。其次我们建立了一个具有多维表征的具体优化模型。该优化模型针对个体列表提出了一个成本模型和大小评估方法，从而计算每个查询树方案解决给定查询图Q所耗费的最小成本。最后，根据最小成本和top-k算法将用于查询的生成树合并成为最优查询计划。我们所提出的基于大型数据图的top-k带环图模式匹配方法，具有高效和精准等优点，在生命科学、软件工程、交互式图形可视化、计算服务发现和3D对象匹配等领域都将有着广泛的应用。3面向图问题的稀疏数据存