|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
; O- b a8 F% v7 d" P- X
ERSearch：一种高效的子图查询算法
6 l2 T' l% q9 u5 u! a4 f: M* f5 c' ]
' E# N* H9 k$ \摘要:子图查询是图数据库研究中的一个重要问题,许多方法基于”过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法 ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌人关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比, ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.
# F7 |# u0 G# r7 u; p' ^9 l关键词:子图查询;特征模式;嵌入关系;图索引;图数据库
9 [, M; F" j5 _% H0 {6 B# _7 b j& Z9 E
" X; I: h* i- s) A% C( s: u1引言
4 P) C, h5 i: ~ {( j ~, g图被广泛用于复杂关系结构的表示,例如蛋白质-蛋白质交互(PPI)网络"、社交网络[2'、通信网络[3、交通网络等.子图查询是图数据管理[5中的核心功能之一,根据数据源和查询目标的不同,子图查询可分为两类:一类的数据源为图集D={G, G2,…, G},给定查询图q之后,需输出D中包含q的数据图集合;另一类子图查询是在某个大型图结构G中,找出与查询图q匹配的部分[67].本文研究为前一类工作.! W5 Z/ S- B# f7 ^/ t9 X+ I
子图同构[8检测是子图查询中的关键操作,这已被证明是一个NP完全[°问题,为了提高子图查询的效率,许多算法使用“过滤-验证”策略:首先挖掘出数据图集所包含的特征模式并构建索引;然后提取出查询图q包含的特征模式集合,若查询图q包含某特征模式f,则所有不包含f的数据图G均不包含q,这些图被排" p. `2 l# z' o2 y* y3 }5 h0 r
. S+ r5 W4 d. A( C+ R7 R
' @, n! H1 K$ e- e% r5 A8 T
5 c- K8 s! c6 R1 z7 S2 c. W |
|
/1 
发表于 2021-1-25 11:32
收藏
淘帖
支持！
反对！