|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
2 G/ r7 Q* _! M6 q+ ~! D% [ERSearch：一种高效的子图查询算法
' y+ X3 [7 o- h( ^$ X' _( c& x1 ]8 z5 M. R
/ A+ m* Z d' V& H
摘要:子图查询是图数据库研究中的一个重要问题,许多方法基于”过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法 ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌人关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比, ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.
7 m7 w5 d1 `; M0 E* F2 N; v w关键词:子图查询;特征模式;嵌入关系;图索引;图数据库' _0 ~# S& K% z' f! N
2 \' Q. w/ }8 f/ D$ g2 n- m
/ o3 l @9 k: a8 g
1引言8 C& |+ ~$ a& L0 l
图被广泛用于复杂关系结构的表示,例如蛋白质-蛋白质交互(PPI)网络"、社交网络[2'、通信网络[3、交通网络等.子图查询是图数据管理[5中的核心功能之一,根据数据源和查询目标的不同,子图查询可分为两类:一类的数据源为图集D={G, G2,…, G},给定查询图q之后,需输出D中包含q的数据图集合;另一类子图查询是在某个大型图结构G中,找出与查询图q匹配的部分[67].本文研究为前一类工作.$ A; {( O5 t: r% J. s a5 W
子图同构[8检测是子图查询中的关键操作,这已被证明是一个NP完全[°问题,为了提高子图查询的效率,许多算法使用“过滤-验证”策略:首先挖掘出数据图集所包含的特征模式并构建索引;然后提取出查询图q包含的特征模式集合,若查询图q包含某特征模式f,则所有不包含f的数据图G均不包含q,这些图被排1 D. n, `# d. x; l
$ x7 l2 u$ O0 w6 @
/ @. @7 m" j3 ~5 E8 Y
$ B; h5 D- s( |, [+ v- L9 U
|
|
/1 
发表于 2021-1-25 11:32
收藏
淘帖
支持！
反对！