首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到17条相似文献,搜索用时 171 毫秒
1.
李瑞远  洪亮 《软件学报》2018,29(6):1792-1812
子图匹配是图论中最基本的操作.研究子图匹配的一个变种,即:在一个节点拥有若干元素的大图数据库中,找到与给定查询图结构同构并且对应节点元素的加权集合包含度大于给定值的所有子图,称作基于包含度的子图匹配(subgraph matching with inclusion degree,简称SMID).该查询能够应用于多种场景,包括论文检索、社区发现、企业招聘等.为高效实现SMID,设计了同时包含节点元素和图结构信息的数据签名与查询签名,在离线处理阶段,利用数据签名为数据图建立动态签名树(DS-Tree),以加快在线处理时图节点的匹配过程.为解决DS-Tree占用空间大的问题,设计了一种DS-Tree压缩方法,在对查询效率影响不大的情况下减小了索引空间.为进一步加快查询效率,还提出了支配子图查询算法.在真实数据和人工数据上的实验结果表明,所提出的方法在效率和扩展性方面优于现有其他方法.  相似文献   

2.
在子图匹配过程中,随着图规模不断增长,匹配时间呈现指数爆炸的趋势.对此,提出一种基于图连通支配集的子图匹配优化算法VF-SMDS.根据贪心算法构建查询图的最小连通支配子图;通过代价模型计算最小连通支配子图节点的匹配代价,构建最优k查询节点匹配序列;通过支配节点的结构特征缩小查询节点搜索空间范围,在数据图中遍历到满足要求的节点,得到最终答案集.实验将VF-SMDS与GADDI、SPath、VF2++、VF3和SubISO方法进行对比.实验结果表明,在处理较大规模子图匹配问题时,VF-SMDS查询效率更高.  相似文献   

3.
传统的子图查询算法大多只在图数据库上进行一次挖掘算法,即在图数据库上建立稳定的数据库索引后将不再对索引进行更新.随着查询兴趣的改变或数据库的频繁更新,原有的数据库索引将不再能提供有用的信息来减少查询过程中候选图的数量.为此,提出一种双索引的子图查询算法,同时在数据库和查询流上挖掘频繁子图并建立索引.子图查询和查询流索引的建立同步进行,即使查询兴趣改变,查询流索引也能自适应地更新索引信息来优化查询效率.针对数据库的频繁更新,查询流索引已提供实时的有效信息,数据库索引无需重新建立.实验结果表明,双索引的结合能有效提高查询子图的处理效率.  相似文献   

4.
《软件》2018,(1):54-59
知识图谱查询是目前知识图谱研究中最广泛的应用,能够有效提高搜索引擎查询效率。然而,现有的知识图谱的查询研究多是基于节点标签的子图匹配。由于节点标签不能体现节点间的语义信息,导致查询结果的语义相关性不高。针对此问题,本文提出了一种基于本体和邻居信息的查询算法OAN(Ontology and Neighborhood)。首先,结合本体相似度和邻居相似度来确定查询节点的候选集,以此提高候选节点的语义相似度;其次,通过边检测算法移除那些不满足条件的查询节点候选集,以此减少查询规模;然后,在目标图上查找满足边标签同构的查询子图,并计算节点的标签相似度和结构相似度总和,给每个结果集打分后排序,获得最终排序后的结果集;最后,通过在真实数据集上与已有查询算法进行对比实验,实验结果表明:本文所提出的方法无论是在精确度上,还是在查询效率方面都有所提高。  相似文献   

5.
将近似子图匹配分成节点匹配和边匹配两个阶段。将数据图中所有节点的h-邻居节点表示成向量形式,采用一种启发式推理算法进行节点匹配得到节点对应关系,使用查询节点权重提高匹配相似度,使用节点过滤、索引技术和孤立候选节点提高运算效率;利用邻居向量索引得到匹配节点集合的扩展图,进行边匹配,得到匹配图。在真实数据上进行实验,实验结果表明,该算法效果较好,运算效率较高,可以应用于节点标签稀疏的情况和top-k近似匹配。  相似文献   

6.
《计算机工程》2017,(9):7-11
节点异质图常作为复杂网络的数据模型,同构子图搜索是异质图挖掘过程中的重要问题,但现有算法的子图去重步骤降低了搜索效率。为此,基于Turbo_(ISO)算法中的邻域等价类(NEC)概念,提出同构子图搜索算法NEC-COMB。该算法包含预处理、节点顺序确定、子图同构匹配和子图提取4个部分,在子图同构匹配时对NEC中的节点使用组合策略,避免等价节点重复匹配。实验结果表明,与经典算法VF2,GraphQL,Turbo_(ISO)相比,NEC-COMB可有效提高搜索效率,优化去重效果。  相似文献   

7.
子图匹配是图数据查询处理技术中的一个重要研究问题。针对现有子图匹配算法运行效率不高且缺乏通用优化方法的现状,提出一种基于社区结构的子图匹配算法优化方法(community structure based subgraph matching optimization method,CSO)。首先,提出两种优化策略,即解析模式图信息以减少子图匹配过程的计算量,以及利用社区结构信息在子图匹配过程中进行剪枝;然后,结合上述两种优化策略提出基于社区结构的子图匹配算法优化方法,并进行了理论分析。真实数据集和合成数据集上的大量实验结果表明,CSO方法能有效减少子图匹配算法的时间开销。同时,不同规模数据集上的实验结果验证了CSO方法良好的可扩展性。  相似文献   

8.
针对大规模数据图下基于回溯法的子图查询算法的准确率低、开销大等问题,为提高查询准确率,降低大图下的查询开销,提出一种基于Spark的子图匹配(SQM)算法。首先根据结构信息过滤数据图,再将查询图分割成基本查询单元;然后对每一个基本查询单元分别匹配后进行Join操作;最后运用并行化提高了算法的运行效率,减小了搜索空间。实验结果表明,与Stwig、TurboISO算法相比,SQM算法在保证查询结果不变的情况下,速度提高了50%。  相似文献   

9.
标签图常用于智能交通网、生物信息网等新兴领域的建模。子图查询作为图数据分析的关键问题,引起了研究者的广泛关注。对现有子图查询算法的研究发现,随着图数据规模增大且频繁更新,传统子图查询算法普遍存在查询效率低,存储开销大,忽略顶点标签信息等问题。为此,提出了一种支持大规模动态标签图子图查询的层次序列索引(Dynamic Hierarchical Sequence,DHS),该索引提取数据图中带有顶点编号的层次拓扑序列关系以实现子图查询;针对图的动态变化,提出了更新点拓扑扩展式索引维护策略,仅从局部变化顶点及边开始进行增量式更新,大大降低了重建索引造成的巨大开销;提出了基于DHS索引的子图查询方法,仅需将查询图与数据图的层次序列进行匹配即可获得候选集,并在其上利用关系匹配策略获得最终查询结果。实验证明提出的方法在保证高效查询的同时降低了索引的创建及维护时间,提高了子图查询效率。  相似文献   

10.
针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K。该方法建立了包括节点拓扑结构特性(NTF)索引和边特性(EF)索引的图拓扑结构特性(GTSF)索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确。大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询。  相似文献   

11.
子图查询返回图数据集合中所有包含查询图的数据图。在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义。不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量。文章详细阐述了α-β子图同构匹配的语义特点,分析了其和期望子图同构的联系和差别,设计实现α-β子图同构匹配判定算法。  相似文献   

12.
近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加困难。针对上述问题,提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引,在序列中加入标号以便数据更新后对索引进行维护,再根据序列间的匹配关系过滤出候选集合,最后采用图同构算法验证候选集中的图,最终得到结果集合。该方法的索引构造简单且体积小,并且在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。  相似文献   

13.
子图同构问题是非确定多项式(NP)完全问题,而轴心子图同构是一种特殊的子图同构问题。针对现在已经有许多高效的子图同构算法,然而对于轴心子图同构问题目前并没有基于GPU的搜索算法,且通过改造已有的子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题,提出了一种基于GPU的轴心子图同构算法。首先,通过一种新颖的多编码树方式,利用节点的标签、度以及节点邻居的结构特征的组合对节点进行编码,并在GPU上对查询图节点并行地进行剪枝,从而明显地减小数据图候选节点所生成的搜索空间树的尺寸;然后,逐层访问查询图节点的候选节点,过滤掉不满足的节点;最后,验证得到的子图是否是查询图的同构子图,从而高效地完成轴心子图同构搜索。实验结果表明,与GPU友好子图匹配(GpSM)算法相比,所提算法的执行时间降低了二分之一,且该算法能够高效地执行轴心子图同构搜索并且具有可扩展性。所提轴心子图同构算法可以减少解决轴心子图同构问题所需的时间,同时降低了GPU内存消耗,提升了算法的性能。  相似文献   

14.
关皓元  朱斌  李冠宇  赵玲 《计算机应用》2018,38(7):1898-1904
针对在SPARQL查询处理中,随着查询图结构逐渐复杂而导致基于图的查询效率愈发低下的问题,通过分析几种资源描述框架(RDF)图的基本结构,提出了一种基于查询图结构切分的子图匹配方法——RSM。首先,将查询图切分为若干结构简单的查询子图,并通过相邻谓词结构索引来定义查询图节点的搜索空间;然后,通过相邻子图结构来缩小搜索空间范围,在数据图中根据搜索空间中的搜索范围找到符合的子图结构;最后,将得到的子图进行连接并作为查询结果输出。将RSM与RDF-3X、R3F、GraSS等主流查询方法作比较,对比了各方法在不同数据集上对于复杂程度不同的查询图的查询响应时间。实验结果充分表明,与其他3种方法相比,在处理结构复杂的查询图时,RSM的查询响应时间更短,具有更高的查询效率。  相似文献   

15.
图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题(CSP)模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。  相似文献   

16.
现有的动态子图匹配研究中忽略了模式图中的时间信息,使用户难以得到想要查询的真实结果.针对这种情况,首先设计一种简洁的中间结果保存形式,将匹配结果直接在数据图中以图进行存储;接着改进边缘转换模型,当数据图有边插入/删除时对其快速增量维护并报告结果;最后根据边转换模型设计了一个时间尊重图模式匹配算法,提高了匹配搜索效率.对真实网络流量数据和综合社交流数据进行实验评估,结果表明算法能够有效减少图模式匹配的执行时间和空间花销.  相似文献   

17.
在SPARQL查询过程中,含有复杂结构的资源描述框架(RDF)图的查询效率低下。为此,通过分析几种RDF图的基本结构与RDF顶点的选择性,提出RDF三元组模式选择性(RTPS)——一种基于RDF顶点选择性的图结构切分规则,以提高面向RDF图的子图匹配效率。首先,根据谓词结构在数据图与查询图中的通性建立RDF相邻谓词路径(RAPP)索引,将数据图结构转化为传入-传出双向谓词路径结构以确定查询顶点的搜索空间,并加快顶点的过滤;接着,通过整数线性规划(ILP)问题计算建模将复杂RDF查询图结构分解为若干结构简单的查询子图,通过分析RDF顶点在查询图中的相邻子图结构与特征,确立查询顶点的选择性以确定最优切分方式;然后,通过RDF顶点选择性与相邻子图的结构特征来缩小查询顶点的搜索空间范围,并在数据图中找到符合条件的RDF顶点;最后,遍历数据图以找到与查询子图结构相匹配的子图结构,将得到的子图进行连接并将其作为查询结果输出。实验采用控制变量法,比较了RTPS、RDF子图匹配(RSM)、RDF-3X、GraSS与R3F的查询响应时间。实验结果充分表明,与其他4种方法相比,当查询图复杂度高于9时,RTPS的查询响应时间更短,具有更高的查询效率。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号