摘要
有向标签图作为重要的数据表示模型,广泛应用于社交网络、语义网分析等信息技术相关的研究领域,子图匹配查询是图数据管理的重要研究问题,引起了研究者的广泛关注.有向标签图的子图同构和子图模拟匹配查询由于代价极高,不适用于大规模图数据的查询处理.本文针对有向标签图,研究基于自适应结构概要的子图匹配查询算法.首先基于图压缩的思想,提出一种满足顶点"局部双拟"关系且具有自适应更新特性的有向标签图结构概要模型,在缩小数据图规模的基础上,适应查询图的结构;然后采用图模拟方式,提出基于自适应结构概要模型的子图匹配查询算法,根据查询图顶点的标签,对与其匹配的结构概要顶点按照其中包含数据图顶点的数量由小到大排序,根据查询图顶点之间的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 adaptive structural summary of graph data.Firstly,we propose adaptive structural summary of graph data based on graph compression.The compressed graph can be adaptively updated according to the structure of query graphs by local bisimulation.The model can reduce the size of graph data and conform to the structure of querygraphs.Secondly,we propose an algorithm for subgraph matching based on adaptive structural summary using graph simulation.According to the nodes in query graphs,each node in the structural summary is ranked in an ascent order.Nodes in structural summary can be matched to those in the query graphs by the distances between ranks of related nodes.Finally,we perform exhaustive experiments on real and synthetic datasets.The results demonstrate that：（1）our adaptive structural summary covers current queries with the lowest space cost;（2）the complexities of time for adaptively updating structural summary and subgraph matching are O（｜E｜log｜V｜）.
出处
《计算机学报》
EI
CSCD
北大核心
2017年第1期52-71,共20页
Chinese Journal of Computers
基金
国家"八六三"高技术研究发展计划项目基金(2013AA013204
2015AA015401)
国家自然科学基金(61170184
61402243)
天津市自然科学基金(13ZCZDGX02200
13ZCZDGX01098
13JCQNJC00100
16JCTPJC53700)资助~~
关键词
有向标签图
局部双拟
结构概要
自适应更新
子图匹配查询
labeled directed graph
local bisimulation
structural summary
adaptive update
subgraph matching
