|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
2 U4 d$ b0 Q, L; [0 I9 k# QERSearch：一种高效的子图查询算法 : u& R9 }& O' u
4 {' H3 E1 b: T4 l
6 J9 R! P* b$ _/ K
摘要:子图查询是图数据库研究中的一个重要问题,许多方法基于”过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法 ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌人关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比, ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.7 _; T9 ^3 u6 ~. z* d- {, L8 r
关键词:子图查询;特征模式;嵌入关系;图索引;图数据库
( t5 l" N; t/ F9 \- x) k
; J2 C) e- [: y* n7 r
: O$ f- B! V$ b! E1引言# l0 b3 L2 a& q ]% f
图被广泛用于复杂关系结构的表示,例如蛋白质-蛋白质交互(PPI)网络"、社交网络[2'、通信网络[3、交通网络等.子图查询是图数据管理[5中的核心功能之一,根据数据源和查询目标的不同,子图查询可分为两类:一类的数据源为图集D={G, G2,…, G},给定查询图q之后,需输出D中包含q的数据图集合;另一类子图查询是在某个大型图结构G中,找出与查询图q匹配的部分[67].本文研究为前一类工作.
: \* S8 v5 z$ w. I! i! u子图同构[8检测是子图查询中的关键操作,这已被证明是一个NP完全[°问题,为了提高子图查询的效率,许多算法使用“过滤-验证”策略:首先挖掘出数据图集所包含的特征模式并构建索引;然后提取出查询图q包含的特征模式集合,若查询图q包含某特征模式f,则所有不包含f的数据图G均不包含q,这些图被排$ ~, W b2 }3 h% J; Z
( v- c4 i! J) Z5 @
8 M( E4 A2 v. Q( w1 ]# O1 P/ Z
9 r; o* U5 x4 B/ }* t+ s+ l5 P
|
|
/1 
发表于 2021-1-25 11:32
收藏
淘帖
支持！
反对！