摘要
图作为一种重要的数据结构，广泛应用于化学研究、社交网络、生物学等诸多领域的实际问题中。子图匹配作为图数据管理的一个研究热点，更是备受关注。随着数据量呈指数级增长，如何在有限的时间内完成计算机内存所能接受的图匹配过程，是研究者面临的挑战。现有的子图匹配算法通常采用过滤和验证策略，适用于规模较小的数据集，图数据规模的增大以及匹配过程中的冗余计算问题使得现有算法在大规模图数据集上的匹配时间复杂度较高。针对以上问题，本课题展开如下的研究： 首先，针对数据图规模较大的问题，提出基于数据图的图压缩算法。根据结点的标签以及拓扑结构，预估结点局部影响值，利用结点局部影响值得出等价结点的判定顺序，通过比较结点标签及邻居结点信息判断是否为等价结点，并以此进行等价结点的划分，同属一个等价类的结点被压缩为一个超结点，最终将数据图压缩为规模较小的超图，有利于大规模图数据的存储和挖掘。 其次，为了提高子图匹配算法的效率，提出基于结点编码的索引构建方式来创建图数据的索引，利用结点度的大小、属性标签、邻域标签滤波器以及结点的包含关系等过滤策略，对索引结构进行剪枝得到结点候选集。 再次，根据查询图结点度及其标签，提出结点信息量的设定方法，并依此得出结点匹配验证的顺序。利用结点等价关系以及组合策略实现对匹配结果的扩充，最终完成整个子图匹配过程。 最后，在不同的真实数据集上对上述算法与已有算法进行对比试验，以验证所提算法的时间效率。
NETL