基于包含度的子图匹配方法

• 作者: 李瑞远 洪亮
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 子图匹配 包含度 图数据库 索引 支配子图
• 年，卷（期）: 2018,（6）
• 所属期刊栏目: 数据库技术
• 页码范围: 1792-1812
• 页数: 21页
• 分类号: TP311
• 字数: 16301字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005268

摘要

子图匹配是图论中最基本的操作.研究子图匹配的一个变种,即:在一个节点拥有若干元素的大图数据库中,找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图,称作基于包含度的子图匹配(subgraph matching with inclusion degree,简称SMID).该查询能够应用于多种场景,包括论文检索、社区发现、企业招聘等.为高效实现SMID,设计了同时包含节点元素和图结构信息的数据签名与查询签名,在离线处理阶段,利用数据签名为数据图建立动态签名树(DS-Tree),以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题,设计了一种DS-Tree压缩方法,在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率,还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明,所提出的方法在效率和扩展性方面优于现有其他方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	洪亮	武汉大学信息管理学院	30	196	9.0	13.0
5	李瑞远	西安电子科技大学计算机学院	1	3	1.0	1.0