主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李瑞远,洪亮.基于包含度的子图匹配方法.软件学报,2018,29(6):1792-1812
基于包含度的子图匹配方法
Method for Subgraph Matching with Inclusion Degree
投稿时间:2016-10-26  修订日期:2017-01-19
DOI:10.13328/j.cnki.jos.005268
中文关键词:  子图匹配  包含度  图数据库  索引  支配子图
英文关键词:mesh parameterization  parameter domain  parameterization quality  bijective mapping  metric distortion
基金项目:国家重点研发计划(2016YFB1000603);国家自然科学基金(61303025);深圳市基础研究项目(JCYJ20160523160953223);NSFC-广东联合基金;国家超级计算广州中心
作者单位E-mail
李瑞远 西安电子科技大学 计算机学院, 陕西 西安 710071  
洪亮 武汉大学 信息管理学院, 湖北 武汉 430072
武汉大学 深圳研究院, 广东 深圳 518000 
hong@whu.edu.cn 
摘要点击次数: 1891
全文下载次数: 2277
中文摘要:
      子图匹配是图论中最基本的操作.研究子图匹配的一个变种,即:在一个节点拥有若干元素的大图数据库中,找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图,称作基于包含度的子图匹配(subgraph matching with inclusion degree,简称SMID).该查询能够应用于多种场景,包括论文检索、社区发现、企业招聘等.为高效实现SMID,设计了同时包含节点元素和图结构信息的数据签名与查询签名,在离线处理阶段,利用数据签名为数据图建立动态签名树(DS-Tree),以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题,设计了一种DS-Tree压缩方法,在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率,还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明,所提出的方法在效率和扩展性方面优于现有其他方法.
英文摘要:
      Subgrpah matching is a basic operation in graph theory. This paper focuses on a variant, namely subgraph matching with inclusion degree (SMID), which retrieves subgraphs that are structurally isomorphic to the query graph while satisfying the condition that the inclusion degree between matched vertexes is greater than a given value. SMID can be applied to many applications, including paper search, crowdsourcing, and recruitment. To efficiently process SMID, this paper designs a novel signature mechanism for data graph and query graph respectively by holding the information of both vertex elements and graph structure. Based on graph signature, a dynamic signature tree (DS-Tree) is built to speed up the SMID processing. A compression method is proposed to reduce the memory usage of DS-Tree. To achieve a better performance, an efficient dominating-set-based subgraph matching algorithm is also developed. Extensive experiments on both real and synthetic datasets demonstrate that the method introduced in this paper outperforms state-of-the-art methods by an order of magnitude in terms of efficiency and scalability.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利