基于模拟匹配的分布式频繁图模式挖掘方法研究

发布时间：2021-01-10 21:32

　　频繁模式挖掘的目标是在数据中找出所有频繁出现的模式,进而发现蕴含在数据中的潜在知识,根据所挖掘数据对象的种类,可以把模式分为事务、序列、项集和图等。在图数据中挖掘频繁的图模式称为频繁图模式挖掘,频繁图模式挖掘的目标是在数据图中找出所有出现次数大于给定最小支持度阈值的图模式。频繁图模式挖掘具有非常重要的理论与应用价值,众多学者也致力于研究新的更高效的频繁图模式挖掘算法。图模式匹配是频繁图模式挖掘算法中的重要操作,在频繁图模式挖掘算法中,通过图模式匹配可以得到当前候选图模式在数据图中的匹配结果,进而判断该图模式是否频繁。按照对匹配结果结构要求是否严格,可以把图模式匹配概念分为精确匹配和模拟匹配两类。当前许多在图数据上进行的频繁图模式挖掘工作都是基于子图同构来实现候选图模式与数据图的精确匹配。子图同构对匹配结果结构约束太过严格,在某些应用中进行挖掘会丢失一些有意义的频繁图模式。模拟匹配允许候选图模式与数据图中的匹配结果存在一定拓扑结构差异,作为一种新兴的匹配概念,在路网监测和社交网络分析等应用中发挥着重要作用。现有的模拟匹配概念,例如图模拟和双向模拟。在频繁图模式挖掘领域,现有的模拟匹配概念... 

【文章来源】： 华冠齐 山东大学

【文章页数】：75 页

【学位级别】：硕士

【部分图文】：

图１－１数据图与图模式??

ｍａｓｔｅｒ－ｓｌａｖｅ?ｍｏｄｅｌ），在主计算节点上执行??ＪｏｂＴｒａｃｋｅｒ，工作节点上执行Ｔａｓｋｔｒａｃｋｅｒ。ｊｏｂＴｒａｃｋｅｒ负责分配计算任务给工作节??点，并与Ｔａｓｋｔｒａｃｋｅｒ进行通信以收集计算结果，Ｔａｓｋｔｒａｃｋｅｒ负责执行ｊｏｂＴｒａｃｋｅｒ??分配的计算任务，并将计算结果返回。??／?Ｍａｓｔｅｒ?）??Ｍａｐ任罗／?＼Ｒｅｄｕｃｅ任务??－｜?＼?ＪＭＡ／ｏｒｋｅｒｌ＾?■■?？?Ｍａｐ结果?｜?Ｉ?｜?Ｉ??子酬１?｜响咖结果??子数据图２??Ｍａｐ结果ｊ?｜?Ｊ??子数据图３?￣＾?｜??＾?数据?Ｒｅｄｕｃｅ结果??——￣?Ｍａｐ结果＇?ｊ?Ｉ?＾＾?Ｉ????图２－１?ＭａｐＲｅｄｕｃｅ计算模型??ＭａｐＲｅｄｕｃｅ核心步骤可以分为两个用户自行编写的函数：映射函数（Ｍａｐ）??与规约函数（Ｒｅｄｕｃｅ），二者均采用ｋｅｙ－ｖａｌｕｅ键值对作为数据处理单元。??１１??

山东大学硕士学位论文??ＭａｐＲｅｄｕｃｅ计算模型如图２－１所示。在计算任务开始时，Ｍａｓｔｅｒ节点将映射任务??分配给各个Ｗｏｒｋｅｒ节点，Ｗｏｒｋｅｒ将当前数据通过一定规则映射为另外的数据，??再将映射后的数据进行排序分组（Ｓｈｕｆｆｌｅ）处理，分配给其他Ｗｏｒｋｅｒ，其他Ｗｏｒｋｅｒ??接到Ｍａｓｔｅｒ的规约任务和处理后的数据，按照规约函数对数据进行规约，得到??最终的运算结果，输出结果也采用键值对格式。??２）?Ｐｒｅｇｅｉ大规模分布式图计算平台??Ｇｏｏｇｌｅ在２０１０年发布的Ｐｒｅｇｅｌ并行图处理系统＾＾是一个可扩展的，容错性??良好的分布式图计算系统。Ｐｒｅｇｅｌ也遵循主从架构和整体同步并行计算模型（Ｂｕｌｋ??Ｓｙｎｃｈｒｏｎｏｕｓ?Ｐａｒａｌｌｅｌ?Ｃｏｍｐｕｔｉｎｇ?Ｍｏｄｅｌ），Ｐｒｅｇｅｌ?由一个唯一的主计算节点和若干??工作节点组成，主计算节点本身不保存整个数据图，也不负责复杂的图计算任务，??而是将整张数据图按照“切边法”切成规模较小的子图，分发给各个工作节点保??存，工作节点只需要维护自身保存数据图的结构。Ｐｒｅｇｅｌ计算模型以结点为中心，??以超步（Ｓｕｐｅｒｓｔｅｐ）为计算单位进行计算，一次计算流程包括若干超步的迭代计??算。在每个超步执行过程中，计算节点执行用户自定义的任务，同时处理上个超??步中接收到的其他节点发来的消息，实现整体同步各个节点并行计算，在分布式??计算领域得到了较为广泛的应用。??超步１?｜超步２?｜超步３?…?｜超步Ｎ??〇?ＫＩ）?Ｊ〇?？〇??０＼?ｘｒＯ??、、ｃ??ｃｒ?ｏ??图２－２?Ｐｒｅｇｅｌ计算模型??图２－２展示了?Ｐｒｅｇｅｌ以


本文编号：2969450