亲爱的研友该休息了!由于当前在线用户较少,发布求助请尽量完整的填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!身体可是革命的本钱,早点休息,好梦!

A subgraph matching algorithm based on subgraph index for knowledge graph

图因式分解 距离遗传图 计算机科学 子图同构问题 图形 诱导子图同构问题 折线图 理论计算机科学 组合数学 匹配(统计) 因子临界图 算法 数学 图形功率 电压图 统计
作者
Yunhao Sun,Guanyu Li,Jingjing Du,Bo Ning,Heng Chen
出处
期刊:Frontiers of Computer Science [Springer Nature]
卷期号:16 (3) 被引量:20
标识
DOI:10.1007/s11704-020-0360-y
摘要

The problem of subgraph matching is one fundamental issue in graph search, which is NP-Complete problem. Recently, subgraph matching has become a popular research topic in the field of knowledge graph analysis, which has a wide range of applications including question answering and semantic search. In this paper, we study the problem of subgraph matching on knowledge graph. Specifically, given a query graph q and a data graph G, the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G. Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph. To accelerate subgraph matching on knowledge graph, we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph, called as FGqT-Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph (FGqT), which reduces redundant calculations in advance. Another design is a multi-label weight matrix, which evaluates a near-optimal matching tree for minimizing the intermediate candidates. With the aid of these two key designs, all subgraph isomorphic mappings are quickly conducted only by traversing FGqT. Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
能干的山雁完成签到 ,获得积分10
3秒前
wangfaqing942完成签到 ,获得积分10
17秒前
42秒前
情怀应助chaoswu采纳,获得10
46秒前
48秒前
53秒前
chaoswu完成签到,获得积分20
57秒前
58秒前
1分钟前
科研通AI5应助ytx采纳,获得10
1分钟前
1分钟前
shimmy发布了新的文献求助10
1分钟前
普通市民7v7完成签到,获得积分10
1分钟前
chaoswu发布了新的文献求助10
1分钟前
1分钟前
ytx发布了新的文献求助10
1分钟前
隐形曼青应助chaoswu采纳,获得10
1分钟前
科研通AI5应助科研通管家采纳,获得10
1分钟前
科研通AI5应助科研通管家采纳,获得10
1分钟前
缪尔岚完成签到,获得积分10
1分钟前
2分钟前
chaoswu发布了新的文献求助10
2分钟前
顾矜应助ytx采纳,获得10
2分钟前
2分钟前
2分钟前
ytx发布了新的文献求助10
2分钟前
传奇完成签到 ,获得积分10
2分钟前
啧啧驳回了桐桐应助
2分钟前
3分钟前
eccentric完成签到,获得积分10
3分钟前
eccentric发布了新的文献求助10
3分钟前
轻松完成签到,获得积分10
3分钟前
研友_VZG7GZ应助ytx采纳,获得10
3分钟前
3分钟前
3分钟前
苗条元霜发布了新的文献求助10
3分钟前
3分钟前
ytx发布了新的文献求助10
3分钟前
3分钟前
科研通AI5应助苗条元霜采纳,获得10
3分钟前
高分求助中
Continuum thermodynamics and material modelling 3000
Production Logging: Theoretical and Interpretive Elements 2700
Healthcare Finance: Modern Financial Analysis for Accelerating Biomedical Innovation 2000
Applications of Emerging Nanomaterials and Nanotechnology 1111
Unseen Mendieta: The Unpublished Works of Ana Mendieta 1000
Les Mantodea de Guyane Insecta, Polyneoptera 1000
工业结晶技术 880
热门求助领域 (近24小时)
化学 医学 材料科学 生物 工程类 有机化学 生物化学 纳米技术 内科学 物理 化学工程 计算机科学 复合材料 基因 遗传学 物理化学 催化作用 细胞生物学 免疫学 电极
热门帖子
关注 科研通微信公众号,转发送积分 3491339
求助须知:如何正确求助?哪些是违规求助? 3077926
关于积分的说明 9151235
捐赠科研通 2770492
什么是DOI,文献DOI怎么找? 1520516
邀请新用户注册赠送积分活动 704589
科研通“疑难数据库(出版商)”最低求助积分说明 702298