图是计算机科学中常见的数据结构,生活中实体与实体之间的关系错综复杂、联系紧密,因此图在众多复杂数据建模中广泛应用,在匹配复杂数据关系的过程中也扮演着越来越重要的角色,如何对图进行有效查询和匹配成为近些年的研究热点。在已提出的子图匹配方法中,首先过滤掉不满足匹配条件的节点,然后再进行边和图的匹配,这称为基于节点的方法。然而这种方法仅仅使用节点信息过滤掉不满足匹配条件的元素,图的边涵盖大量的信息却没有效利用。近似子图是指不缺失查询图的任何节点,而只丢失一定数量的边,而边丢失的数量处在一定范围内,这个阈值称为容忍度K。噪声因素使图的边信息丢失变得常见,即便在边缺失的情形下,也要找到查询图的近似匹配子图以备研究和分析。因此,本文提出了图的基于边的近似子图匹配方法。首先,提出图的边标签索引,它能实现对图的高效过滤和查询。充分利用边的索引信息,在查询检索阶段不仅能过滤掉不合格(不匹配)的节点和边,也避免了匹配阶段进行不必要的节点、边连通性检测,从而减少了算法的冗余匹配步骤。其次,对给定的查询图进行预处理,生成查询图的近似子图查询边序和精确子图查询边序进行查询和匹配。最后,引入改进的位串向量数据结构,对被查询图的子图进行子图匹配验证和连通性检测,从而提高图的子图匹配效率,减少冗余的子图匹配步骤。在真实数据集和合成数据集上,将本文提出的KTSM方法和现有的GADDI、 SAPPER等方法进行对比,在分别变化四种参数时的实验结果进行比较和分析,验证了本文提出的子图匹配方法在现实图网络和合成数据集上,都具有较好的查询匹配能力,子图匹配的效率得到了极大的提高。