|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
' V d8 ^ }9 ~# C$ IERSearch：一种高效的子图查询算法 % S6 C0 a% n, a3 B! e" [- X, N% A
) T0 y/ F2 L/ g3 L
j M1 S5 H2 c& F; O0 w$ }! C摘要:子图查询是图数据库研究中的一个重要问题,许多方法基于”过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法 ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌人关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比, ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率. {0 U% i0 ]3 K
关键词:子图查询;特征模式;嵌入关系;图索引;图数据库/ j% L8 O* _( d" `
# c2 M# U! n6 d0 g# h3 N1 x2 M& I
' i0 S! N4 |% O% w1引言
/ s3 }6 i) u" [1 j5 c图被广泛用于复杂关系结构的表示,例如蛋白质-蛋白质交互(PPI)网络"、社交网络[2'、通信网络[3、交通网络等.子图查询是图数据管理[5中的核心功能之一,根据数据源和查询目标的不同,子图查询可分为两类:一类的数据源为图集D={G, G2,…, G},给定查询图q之后,需输出D中包含q的数据图集合;另一类子图查询是在某个大型图结构G中,找出与查询图q匹配的部分[67].本文研究为前一类工作.
0 `) c1 f3 j0 B9 G M子图同构[8检测是子图查询中的关键操作,这已被证明是一个NP完全[°问题,为了提高子图查询的效率,许多算法使用“过滤-验证”策略:首先挖掘出数据图集所包含的特征模式并构建索引;然后提取出查询图q包含的特征模式集合,若查询图q包含某特征模式f,则所有不包含f的数据图G均不包含q,这些图被排
' s4 c+ k% X; K
1 [7 ~( I4 z+ a% h% Y% @8 C% ^1 N B9 e) Z( W" r8 t1 m; G
: I8 a8 t4 G9 E- Z; \ |
|
/1 
发表于 2021-1-25 11:32
收藏
淘帖
支持！
反对！