论文部分内容阅读
目前,关联性数据规模巨大,增长迅速,通过数据关联性,从海量数据中抽取有价值信息是大数据计算的核心,由于图适合表示数据关联性,图可以对海量数据中提取有价值的信息起到很大作用,因此大规模图计算技术成为当前大数据学术研究和工业研究的热点。 作为实现图计算技术的基本方法,图匹配技术在许多相关的学术领域中被广泛研究,包括社会安全分析、网络攻击检测、生物分析、商品推荐等。然而,由于当前进入大数据时代,数据量和数据复杂程度的增加给图匹配技术也带来了新的挑战:(1)图模式匹配问题复杂且运算耗时,其时间复杂度随着图数据节点规模的增长呈指数性增长;(2)图模式匹配问题中的模式图往往以集合的方式出现,但已有的图模式匹配算法将要匹配的模式图看成独立的个体,单独进行匹配计算,造成整个模式图集的计算过程中存在大量对相同结构的重复计算,使得整体匹配过程存在冗余时间消耗。 当前,已有的图模式匹配算法主要从优化剪枝策略,对数据图建立索引等方面进行改进,对所有的模式图独立地在数据图上进行查找。然而这种把要匹配的模式图看成独立的个体,忽略了模式图集中结构相关性的方式,会造成大量的相同结构的重复计算,消耗过多冗余时间。为了利用模式图集中模式图之间的结构相关性,本文主要从三个方面开展基于结构相关性的多模式图匹配技术的研究,包括:基于多模式图索引的图匹配技术,多模式图的结构相关性挖掘技术,多模式图匹配算法库的设计与实现。本文的主要贡献总结如下: (1)提出了一种基于结构相关性的多模式图索引,并提出了一种新的利用多模式图索引来进行精确图匹配的加速框架。该框架可以与现有的图模式匹配算法相结合,加速多模式图匹配的计算速度。多模式图索引记录了模式图之间最优的结构相关性,重新安排多模式图进行图匹配的计算顺序,避免相同结构的重复计算。通过在真实数据集和合成数据集上进行实验,本文证明了基于多模式图索引的图匹配技术的有效性和扩展性,在实验所用的真实与合成的数据集上,该技术与现有算法相比,可提升匹配平均速度2倍到一个数量级不等。 (2)提出多模式图的结构相关性挖掘技术。在多模式图索引的图匹配技术的基础上,为了优化该技术在部分模式图包含关系较少的数据集上的效果,多模式图的结构相关性挖掘技术通过挖掘模式图中的频繁子图,选择挖掘出的频繁子图中合适的一部分,加入到多模式图索引中,优化多模式图索引结构,从而提升多模式图匹配技术的计算性能。 (3)在上述关键技术的基础上,设计并实现了一个多模式图匹配算法库。多模式图匹配算法库提供了多模式图查询和单模式图查询的多种算法接口,提供了多种算法库可用的测试数据集,设计并实现了用户友好的算法库交互界面。