|
|
|
|
【英文篇名】 |
An Algorithm for Subgraph Matching Based on Adaptive Structural Summary of Labeled Directed Graph Data |
|
【下载频次】 |
★★★★★ |
|
【作者】 |
张海威;
解晓芳;
段媛媛;
温延龙;
张莹;
袁晓洁; |
|
【英文作者】 |
ZHANG Hai-Wei;
XIE Xiao-Fang;
DUAN Yuan-Yuan;
WEN Yan-Long;
ZHANG Ying;
YUAN Xiao-Jie;
College of Computer and Control Engineering;
Nankai University;
College of Software; |
|
【作者单位】 |
南开大学计算机与控制工程学院;
南开大学软件学院; |
|
【文献出处】 |
计算机学报
, Chinese Journal of Computers, 编辑部邮箱
2017年 01期
期刊荣誉：中文核心期刊要目总览 ASPT来源刊 中国期刊方阵 CJFD收录刊 |
|
【中文关键词】 |
有向标签图;
局部双拟;
结构概要;
自适应更新;
子图匹配查询; |
|
【英文关键词】 |
labeled directed graph;
local bisimulation;
structural summary;
adaptive update;
subgraph matching; |
|
【摘要】 |
有向标签图作为重要的数据表示模型,广泛应用于社交网络、语义网分析等信息技术相关的研究领域,子图匹配查询是图数据管理的重要研究问题,引起了研究者的广泛关注.有向标签图的子图同构和子图模拟匹配查询由于代价极高,不适用于大规模图数据的查询处理.本文针对有向标签图,研究基于自适应结构概要的子图匹配查询算法.首先基于图压缩的思想,提出一种满足顶点局部双拟关系且具有自适应更新特性的有向标签图结构概要模型,在缩小数据图规模的基础上,适应查询图的结构;然后采用图模拟方式,提出基于自适应结构概要模型的子图匹配查询算法,根据查询图顶点的标签,对与其匹配的结构概要顶点按照其中包含数据图顶点的数量由小到大排序,根据查询图顶点之间的rank差值在结构概要模型中实现顶点匹配;最后在真实数据集和模拟数据集上进行实验,结果表明:(1)自适应结构概要模型可根据查询图结构,实现对数据图的最大压缩;(2)可在O(|E|log|V|)的总体时间复杂度内实现结构概要的自适应更新以及基于图模拟方式的子图匹配查询. |
|
【英文摘要】 |
Labeled directed graph,as one of the essential data models,has been widely used in many research areas,such as social network,semantic web analysis and so on.Subgraph matching is an important problem of graph data management and has drawn more and more attention of researchers.Traditional method of subgraph matching such as isomorphism matching and simulation matching cannot handle the large graph for their complexities of time.In this paper,we propose an efficient algorithm for subgraph matching based on a... |
|
【基金】 |
国家“八六三”高技术研究发展计划项目基金(2013AA013204,2015AA015401);
国家自然科学基金(61170184,61402243);
天津市自然科学基金(13ZCZDGX02200,13ZCZDGX01098,13JCQNJC00100,16JCTPJC53700)资助~~ |
|
【更新日期】 |
2017-02-13 |
|
【分类号】 |
O157.5 |
|
【正文快照】 |
graphs.Secondly,we propose an algorithm for subgraph matching based on adaptive structuralsummary using graph simulation.According to the nodes in query graphs,each node in the structuralsummary is ranked in an ascent order.Nodes in structural summary can |
|
| 【相似文献】 |
 |
中国期刊全文数据库 |
 |
|
|
中国优秀硕士学位论文全文数据库 |
|
|
|
中国博士学位论文全文数据库 |
|
|
|
中国重要会议论文全文数据库 |
|
|
|
中国重要报纸全文数据库 |
|
|
|
中国学术期刊网络出版总库 |
|
|
|
|
点击下列相关研究机构和相关文献作者，可以直接查到这些机构和作者被《中国知识资源总库》收录的其它文献，使您全面了解该机构和该作者的研究动态和历史。
|
|
【文献分类导航】从导航的最底层可以看到与本文研究领域相同的文献，从上层导航可以浏览更多相关领域的文献。
|
|
|
| 
推荐 
