一种基于自适应结构概要的有向标签图子图匹配查询算法
发布时间：2018-09-08 16:13
【摘要】：有向标签图作为重要的数据表示模型,广泛应用于社交网络、语义网分析等信息技术相关的研究领域,子图匹配查询是图数据管理的重要研究问题,引起了研究者的广泛关注.有向标签图的子图同构和子图模拟匹配查询由于代价极高,不适用于大规模图数据的查询处理.本文针对有向标签图,研究基于自适应结构概要的子图匹配查询算法.首先基于图压缩的思想,提出一种满足顶点"局部双拟"关系且具有自适应更新特性的有向标签图结构概要模型,在缩小数据图规模的基础上,适应查询图的结构;然后采用图模拟方式,提出基于自适应结构概要模型的子图匹配查询算法,根据查询图顶点的标签,对与其匹配的结构概要顶点按照其中包含数据图顶点的数量由小到大排序,根据查询图顶点之间的rank差值在结构概要模型中实现顶点匹配;最后在真实数据集和模拟数据集上进行实验,结果表明:(1)自适应结构概要模型可根据查询图结构,实现对数据图的最大压缩;(2)可在O(|E|log|V|)的总体时间复杂度内实现结构概要的自适应更新以及基于图模拟方式的子图匹配查询.
[Abstract]:As an important data representation model, directed label graph is widely used in the research fields of information technology, such as social network, semantic web analysis and so on. Subgraph matching query is an important research problem in graph data management, which has attracted extensive attention of researchers. The subgraph isomorphism of directed label graph and the subgraph simulated matching query are not suitable for the query processing of large-scale graph data due to the high cost. In this paper, a subgraph matching query algorithm based on adaptive structure summary is studied for directed label graph. Firstly, based on the idea of graph compression, a structure summary model of directed label graph is proposed, which satisfies the vertex "local double fitting" relation and has the characteristic of adaptive updating. On the basis of reducing the scale of data graph, it adapts to the structure of query graph. Then a subgraph matching query algorithm based on adaptive structure summary model is proposed by using graph simulation. According to the label of query graph vertices, the matching structure summary vertices are sorted according to the number of vertices containing data graph from small to large. According to the rank difference between the vertices of the query graph, the vertex matching is realized in the structure summary model. Finally, the experiments are carried out on the real data set and the simulated data set. The results show that: (1) the adaptive structure summary model can be based on the structure of the query graph. The maximum compression of the data graph is realized. (2) the adaptive updating of the structure outline and the query of subgraph matching based on graph simulation can be realized within the total time complexity of O (E?
【作者单位】： 南开大学计算机与控制工程学院;南开大学软件学院;
【基金】：国家“八六三”高技术研究发展计划项目基金(2013AA013204,2015AA015401) 国家自然科学基金(61170184,61402243) 天津市自然科学基金(13ZCZDGX02200,13ZCZDGX01098,13JCQNJC00100,16JCTPJC53700)资助~~
【分类号】：O157.5
[Abstract]:As an important data representation model, directed label graph is widely used in the research fields of information technology, such as social network, semantic web analysis and so on. Subgraph matching query is an important research problem in graph data management, which has attracted extensive attention of researchers. The subgraph isomorphism of directed label graph and the subgraph simulated matching query are not suitable for the query processing of large-scale graph data due to the high cost. In this paper, a subgraph matching query algorithm based on adaptive structure summary is studied for directed label graph. Firstly, based on the idea of graph compression, a structure summary model of directed label graph is proposed, which satisfies the vertex "local double fitting" relation and has the characteristic of adaptive updating. On the basis of reducing the scale of data graph, it adapts to the structure of query graph. Then a subgraph matching query algorithm based on adaptive structure summary model is proposed by using graph simulation. According to the label of query graph vertices, the matching structure summary vertices are sorted according to the number of vertices containing data graph from small to large. According to the rank difference between the vertices of the query graph, the vertex matching is realized in the structure summary model. Finally, the experiments are carried out on the real data set and the simulated data set. The results show that: (1) the adaptive structure summary model can be based on the structure of the query graph. The maximum compression of the data graph is realized. (2) the adaptive updating of the structure outline and the query of subgraph matching based on graph simulation can be realized within the total time complexity of O (E?
【作者单位】： 南开大学计算机与控制工程学院;南开大学软件学院;
【基金】：国家“八六三”高技术研究发展计划项目基金(2013AA013204,2015AA015401) 国家自然科学基金(61170184,61402243) 天津市自然科学基金(13ZCZDGX02200,13ZCZDGX01098,13JCQNJC00100,16JCTPJC53700)资助~~
【分类号】：O157.5
【相似文献】
相关期刊论文 前10条
1 聂志峰,王昌田,聂峻峰;自适应结构补偿器的研究[J];山东科技大学学报(自然科学版);2003年01期
2 隋允康,邵建义;自适应结构多工况下强度控制的研究[J];力学学报;2002年02期
3 张连文,夏人伟,曾广武;自适应结构频率和阻尼比的计算[J];应用数学和力学;1999年06期
4 庞勤;;2010年的AIAA力学国际会议[J];强度与环境;2009年03期
5 罗晓平;黄海;;自适应桁架结构振动控制及其PCL仿真[J];机械科学与技术;2007年01期
6 于明;二维自适应结构网格的变分生成方法[J];计算物理;2004年01期
7 朱德懋,张方,陈国平;自适应结构减振技术[J];应用力学学报;2001年S1期
8 隋允康,邵建义;自适应超静定桁架结构强度控制的研究[J];固体力学学报;2001年02期
9 陈勇,陶宝祺,高，
本文编号：2231033
本文链接：https://www.wllwen.com/kejilunwen/yysx/2231033.html
