高效低索引的图相似性搜索算法.pdf
《高效低索引的图相似性搜索算法.pdf》由会员分享,可在线阅读,更多相关《高效低索引的图相似性搜索算法.pdf(9页珍藏版)》请在咨信网上搜索。
1、h t t p:/ww wj s j k x c o mD O I:/j s j k x 到稿日期:返修日期:基金项目:江苏省高校自然科学研究项目(K J A )T h i sw o r kw a ss u p p o r t e db yt h eN a t u r a lS c i e n c eF o u n d a t i o no f t h eJ i a n g s uH i g h e rE d u c a t i o nI n s t i t u t i o n so fC h i n a(K J A )通信作者:郑朝晖(z h e n g z h s u d a e d u
2、c n)高效低索引的图相似性搜索算法邱珍郑朝晖苏州大学计算机科学与技术学院江苏 苏州 江苏省网络空间安全工程实验室江苏 苏州 (s t u s u d a e d u c n)摘要图相似性搜索是在给定的度量标准下查找与查询图相似的图集合,目前大多采用“过滤验证”的计算框架.针对现有方法中过滤下界不紧密和索引空间占用较大等问题,提出了一种基于查询图分区的多层级过滤、低索引空间占用的图相似性搜索算法Z I n d e x.该算法首先通过全局粗粒度过滤得到预候选集;然后提出基于扩展概率的查询图分区算法,并采用层级过滤机制进一步精简候选集,增强下界紧密性;最后引入序列相似性差值计算序列中数据分布的稀疏
3、度,提出分区压缩和差值压缩两种编码压缩算法,并据此构建“零”索引结构,降低索引空间开销.实验结果表明,Z I n d e x算法所得下界更加紧密,产生的候选集大小可减少 左右,算法执行时间大大缩短,且该算法在索引空间占用极小的情况下仍具有可扩展性.关键词:图相似性搜索;层级过滤;扩展概率;编码压缩;查询图分区中图法分类号T P G r a p hS i m i l a r i t yS e a r c hw i t hH i g hE f f i c i e n c ya n dL o wI n d e xQ I UZ h e na n dZ HE NGZ h a o h u iS c h o
4、 o l o fC o m p u t e rS c i e n c ea n dT e c h n o l o g y,S o o c h o wU n i v e r s i t y,S u z h o u,J i a n g s u ,C h i n aJ i a n g s uP r o v i n c eC y b e r s p a c eS e c u r i t yE n g i n e e r i n gL a b o r a t o r y,S u z h o u,J i a n g s u ,C h i n aA b s t r a c t G r a p hs i m
5、i l a r i t ys e a r c h i s t os e a r c ht h eg r a p hs e t t h a t i s s i m i l a r t oq u e r yg r a p hu n d e r am e a s u r e m e n t,w h i c ha d o p t s t h e“f i l t e r i n g v e r i f i c a t i o n”f r a m e w o r k A i m i n ga t t h ep r o b l e m so f t h e e x i s t i n gm e t h o
6、d s,s u c ha s t h eu n t i g h t l o w e rb o u n da n d t h e l a r g ei n d e xs p a c e,a n i m p r o v e dg r a p hs i m i l a r i t ys e a r c ha l g o r i t h m(Z I n d e x)b a s e do nq u e r yg r a p hp a r t i t i o nw i t hm u l t i l e v e l f i l t e r i n ga n dl o wi n d e xs p a c e
7、i sp r o p o s e d F i r s t l y,t h ep r e c a n d i d a t es e t i so b t a i n e db yg l o b a l c o a r s e g r a i n e df i l t e r i n g S e c o n d l y,aq u e r yg r a p hp a r t i t i o n i n ga l g o r i t h mb a s e do ne x t e n s i o np r o b a b i l i t yi sp r o p o s e d,a n dah i e r
8、 a r c h i c a lf i l t e r i n gm e c h a n i s mi sa d o p t e dt of u r t h e rs h r i n kt h e c a n d i d a t e s e t,s oa s t oe n h a n c e t h e t i g h t n e s s o f t h e l o w e rb o u n d F i n a l l y,t h e s e q u e n c e s i m i l a r i t yd i f f e r e n c e i s i n t r o d u c e dt
9、o c o m p u t e t h e s p a r s i t yo f t h ed a t a c o n t r i b u t i o n T h e np a r t i t i o nc o m p r e s s i o na n dd i f f e r e n c e c o m p r e s s i o na l g o r i t h ma r ep r o p o s e d t oc o n s t r u c t“z e r o”i n d e xs t r u c t u r e,s oa s t or e d u c e t h e i n d e x
10、s p a c e E x p e r i m e n t a l r e s u l t ss h o wt h a tZ I n d e xa l g o r i t h mh a sa t i g h t e rl o w e rb o u n d,a n dt h ec a n d i d a t es e t s i z eo fZ I n d e xc a nb er e d u c e da b o u t M o r e o v e r,t h ea l g o r i t h me x e c u t i o nt i m e i sg r e a t l yr e d u
11、c e d,a n d i t s t i l l s h o w sg r e a t s c a l a b i l i t y i nt h ec a s eo f t i n y i n d e xs p a c e K e y w o r d s G r a p hs i m i l a r i t ys e a r c h,H i e r a r c h i c a l f i l t e r i n g,E x t e n s i o np r o b a b i l i t y,C o d i n gc o m p r e s s i o n,Q u e r yg r a p
12、hp a r t i t i o n i n g引言近年来,随着互联网技术的飞速发展,数据量呈指数级增长,实现数据的高效存储与检索至关重要.在大数据时代,由于数据实体具有各自的特征属性且大量数据之间存在相互关联的复杂关系,因此通常将这些数据实体以及数据之间的关系抽象为图结构.面对大规模图数据集,图相似性搜索算法在数据分析中具有重要意义,且已被广泛应用于各个领域,如生化信息学、计算机视觉、模式识别和数据检索等 .在图数据集中,对于给定的查询图q和编辑距离阈值,根据指定的图相似性度量标准检索所有编辑距离不超过的图g的过程被称为图相似性搜索.目前,评估图相似性的度量标准有图编辑距离、最大公共子图和图
13、对齐等.其中,图编辑距离(G r a p hE d i tD i s t a n c e,G E D)作为最常用的度量指标,几乎可以评估所有类型的图,精确计算图之间的结构差异.由于图编辑距离计算是N P H a r d问题,因此现有方法大多采用“过滤验证”的思路求解图相似性搜索问题,其性能主要取决于候选集大小、过滤得到候选集的代价,以及图编辑距离的计算开销.在过滤阶段,通常采用索引构建算法和上下界剪枝策略来快速过滤不满足阈值约束的数据图,得到候选集.但过于松弛的过滤下界会导致候选集过大,设计较优的索引结构能缓解这一问题,但会导致索引空间占用较多,然而大部分研究没有考虑到这一性能瓶颈.在验证阶段
14、,要分别精确计算查询图与候选集中数据图的图编辑距离,该过程需要较大的计算开销.如果过滤阶段能够得到精简的候选集,则会大大降低验证阶段的时间消耗.因此,设计高效的过滤机制是优化图相似性搜索算法的重要一环,本文会对该过程做进一步的优化.针对上述候选集较大和索引空间占用较大等问题,本文对过滤策略做出改进并优化索引空间,提出了一种基于查询图分区的多层级过滤、低索引空间占用的图相似性搜索算法Z I n d e x,并在不同数据集上进行实验验证.实验结果表明,本文算法能够在低索引空间占用下实现高效查询.主要工作总结如下:)提出了一种基于扩展概率的查询图分区算法,为每个分区引入一个扩展概率值,即顶点或边被分
15、配到当前分区的可能性,将复杂的结构分区过程转换为简单的数值比较,根据该值可以更精确地判断一个分区与数据图是否匹配,提高了过滤效果.)提出了层级过滤机制以减少候选集大小.为避免不必要的分区匹配与索引构建,在对查询图分区之前首先采用粗粒度过滤得到预候选集,然后在分区过程中基于子图匹配方法进行过滤以进一步精简候选集,解决了候选集过大的问题.)不同于其他研究者对数据库中的图进行分区,本文对查询图分区并建立索引,为每个索引序列引入元素相似性差值,来表征该序列的数据分布稀疏度,并在此基础上提出分区压缩和差值压缩两种编码压缩算法,进而建立“零”索引结构,在降低索引空间的同时大大加快了过滤速度,缓解了在海量数
16、据图中构建索引带来的空间压力.相关工作与问题定义 相关工作针对图相似性搜索问题,国内外学者开展了诸多广泛的研究 .在验证阶段,常用的图编辑距 离算 法 有:AG E D,D F_G E D,D D F,C S I_G E D,A s t a r L S a 和B S S_G E D 等.在过滤阶段,W a n g等 提出了基于树的qg r a m和基于路径的q g r a m,通过构建k A T树过滤筛选不符合下界条件的数据图,将k A T索引组织为倒排索引以避免缓慢的顺序搜索,不足之处在于该方法只适用于稀疏图.此后,Z h e n g等提出了分支距离的概念,设计了新的下界过滤机制,但 其 算
17、 法 的 时 间 和 空 间 复 杂 度 较 高.在 此 基 础 上,Z h e n g等 又提出了基于种过滤边界的混合过滤方法.上述过滤方法都采用了固定划分子结构的思想,由于子结构之间存在重叠部分,一次图编辑操作可能会影响多个子结构,因此该方法的过滤效果有待优化.针对该问题,Z h a o等 首次提出了不相交图划分 的思想P a r s,将数据图划分为个非重叠子结构,通过子图同构计算过滤数据图,其缺点在于需要较长的索引构造时间和子图同构计算时间,而且随机分区方法会对识别假阳性图造成干扰.此后,L i a n g等 提出了参数化的下界和选择性图划分方法ML P a r t i t i o n.
18、该方法可以识别更多的假阳性图,减少候选集大小,而对于大量数据图而言,图划分、子图同构计算和倒排索引的构建均需占据大量的时间与空间.虽然目前已有各种优化的图相似性搜索算法,但是部分改进后的算法仍存在下界不紧密的问题,过滤比例仍然较低,且大多数研究未考虑索引空间占用较大引起的空间消耗问题.基于此,本文提出了一种高效低索引的图相似性搜索算法,在获得较小候选集的同时,能够保证索引占用较低.问题定义本文中,将带标签图集合G定义为一个三元组:GV,E,L.其中V表示图G中的顶点集合,EVV表示边集合,L表示标签标记函数.对于一个数据图gG,用Vg和Eg分别表示图g中的顶点和边集合,用|Vg|和|Eg|分别
19、表示图g中的顶点和边的数量,|G|表示图集合G中数据图的数量.定义(图编辑距离,G r a p hE d i tD i s t a n c e,G E D)数据图g转换为查询图g 所需的最少编辑距离操作数,用来衡量两个图之间的结构差异.本文使用G E D(g,g)表示图g和g 之间的编辑距离.其中图编辑距离操作包括以下点:)插入一个新的孤立顶点u;)在已有顶点u和v之间插入新边e,e(u,v);)删除一个孤立顶点u;)删除连接顶点u和v的边e,e(u,v);)修改顶点v的标签;)修改边e的标签.例如图所示,给定两个图g和g,则G E D(g,g).其中,g转换为g的编辑操作步骤具体体现为:)删
20、除连接顶点C,D的边;)删除连接顶点A,F的边;)删除连接顶点C,F的边;)删除顶点F;)将顶点C修改为E.图查询图q和数据图g,gF i g Q u e r yg r a p hqa n dd a t ag r a p h sg,g定义(不相交图分区)将数据图根据特定规则划分成两两互斥的独立子结构.在本文Z I n d e x算法中,对于一个给定的图g,将满足以下条件的分区结果表示为P(g)p,p,pi.)i,piP(g);)i,j且ij,VpiVpj;)Vni Vpi,Eni Epi.在Z I n d e x算法的 分 区 过 程 中,为 解 决 固 定 分 区 导 致的下界松散问题,提
21、升 过滤 性能,本文 提出 了 基于 扩展 概率的查询图分区 算法,通过 引入 扩展 概 率值,动 态 计算 图中各顶点与边的匹配情况,最终得到满足上述不相交条件邱珍,等:高效低索引的图相似性搜索算法的图分区集合P(q).例如图所示,查询图q被分为个分区,即P(q)p,p,p,p.其中任意两个分区都不存在重叠部分,且所有分区的并集为完整的图q.图查询图q的分区情况F i g P a r t i t i o n so fq u e r yg r a p hq定义(图相似性搜索)图相似性搜索算法指从一个给定的数据图集合G中查找与某一查询图q的编辑距离小于或等于阈值的所有数据图g的集合R.定义如下:
22、Rg|G E D(g,q)()例如图所示,给定图数据集Gg,g 和查询图q,设编辑 距 离 阈 值,分 别 求 得G E D(g,q),G E D(g,q),其中满足编辑距离阈值的数据图为g,则Rg.定义(过滤下界)对于图g和q,本文定义编辑距离下界L B(g,q)来实现数据图的过滤,如果G E D(g,q)L B(g,q),即过滤下界大于编辑距离阈值,则图g可被过滤,不用精确计算图编辑距离.因此,过滤下界越紧密,越接近真实G E D,所得候选集就越小,算法性能越好.算法设计与分析本文Z I n d e x算法 主 要 包 括 以 下个 重 要 组 成 部 分:)首先基于扩展概率对查询图做分区
23、处理,用查询子图去匹配数据库中的图;)采用层级过滤机制精简候选集,以此减少验证阶段中图编辑距离的计算次数;)最后基于编码压缩算法构建“零”索引,降低索引空间占用,使得能在有限的空间内实现高效查询.本文Z I n d e x算法流程图如图所示,其中,l表示预设的序列压缩阈值,g a p表示任一序列的元素相似性差值.图Z I n d e x算法流程图F i g F l o wc h a r to fZ I n d e xa l g o r i t h m 基于扩展概率的查询图分区算法基于固定大小子结构的图分区方法存在以下缺点:)忽略了图的拓扑结构信息,随着数据规模的增大,其可扩展性存在局限性;)固
24、定大小子结构存在大量结构冗余,一次图编辑距离操作可能会影响多个子结构,导致下界过于松散.为增强下界紧密性,提升过滤性能,Z I n d e x算法针对分区过程中各区域的匹配情况,提出了基于扩展概率的查询图分区算法.不同于P a r s 对图数据库中所有数据图进行随机分区进而造成分区冗余,本文对查询图集合根据定义进行不相交图划分,通过引入扩展概率值的概念,将查询图划分为k个非重叠子区域,其中为编辑距离阈值,k为下界参数值.对于一个分区pi而言,其扩展依据为分区大小和分区中顶点与边标签出现的频率.其中,分区大小表示该分区中顶点和边的总数量,即|VPi|EPi|;顶点标签频率表示该分区所有顶点中每一
25、类顶点出现的次数,即vVPif(Lv);同理,边标签频率表示为eEPif(Le).如果查询图中某一分区较大,那么它就越有可能被编辑距离操作所影响,越不容易被匹配到.同理,分区pi中顶点和边标签频率越高,那么它在数据图中出现的概率也越大,越容易被匹配到.因此,根据扩展概率值s(pi)可以快速判断分区pi与图g是否匹配,大大提高过滤效果.对分区pi而言,其扩展概率值s(pi)的定义如下:s(pi)vEPif(Lpi(v)|Vpi|eEpif(Lpi(e)|Epi|Vpi|Epi|()其中,f(Lpi(v)表示分区pi中顶点标签为v的顶点数量;f(Lpi(e)同理.s(pi)值越大,表明分区pi越容
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高效 索引 相似性 搜索 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。