期刊文献+
共找到18篇文章
< 1 >
每页显示 20 50 100
动态图模式匹配技术综述 被引量:14
1
作者 许嘉 张千桢 +2 位作者 赵翔 吕品 李陶深 《软件学报》 EI CSCD 北大核心 2018年第3期663-688,共26页
随着大数据时代的到来,多源异构数据的快速增长已经成为开放性问题,数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中,例如网络安全分析和社交网络舆情分析,描述实体对象之间关系的图数据的结构和内容往往不是固定不变... 随着大数据时代的到来,多源异构数据的快速增长已经成为开放性问题,数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中,例如网络安全分析和社交网络舆情分析,描述实体对象之间关系的图数据的结构和内容往往不是固定不变的,图数据的结构以及节点和边的属性会随着时间的推移发生更新变化.因此,如何在动态更新的图数据中进行高效的查询、匹配,是目前研究的热点问题.从关键技术、代表性算法和性能评价方面概述动态图模式匹配技术的研究进展.最后,对动态图模式匹配技术的典型应用、面临的挑战问题和未来发展趋势进行了总结和展望. 展开更多
关键词 动态 图模式匹配 同构 匹配算法 搜索
下载PDF
面向模式图变化的增量图模式匹配 被引量:4
2
作者 张丽霞 王伟平 +1 位作者 高建良 王建新 《软件学报》 EI CSCD 北大核心 2015年第11期2964-2980,共17页
在大数据时代,数据图的规模急剧增长,增量图模式匹配算法能够在数据图或模式图发生变化时避免重新在整个数据图上进行匹配、减少响应时间,因此成为了研究的热点.针对实际应用中数据图不变而模式图发生变化的情况,提出了一种面向模式图... 在大数据时代,数据图的规模急剧增长,增量图模式匹配算法能够在数据图或模式图发生变化时避免重新在整个数据图上进行匹配、减少响应时间,因此成为了研究的热点.针对实际应用中数据图不变而模式图发生变化的情况,提出了一种面向模式图变化的增量图模式匹配算法PGC_Inc GPM,在模式图匹配的过程中记录适当的中间结果作为索引,用于后续的模式匹配.提出了增强的图模式匹配算法GPMS,用于首次整个数据图上的模式匹配.该算法一方面能够建立后续增量匹配所需的索引,另一方面减少了整个数据图匹配的执行时间.设计实现了面向模式图增边和减边的两个核心子算法,通过子算法的组合,能够支持在模式图发生各种变化时进行增量图模式匹配.在真实数据集和合成数据集上进行实验,结果表明:与重新在整个数据图上进行匹配的Re Computing算法相比,当模式图中变化的边的数目不超过不变的边的数目时,PGC_Inc GPM算法能够有效减少图模式匹配的执行时间;随着数据图规模的增大,PGC_Inc GPM算法相对于Re Computing算法的执行时间的减少程度更加明显,对于大规模数据图具有更好的适用性. 展开更多
关键词 图模式匹配 增量算法 动态 大数据
下载PDF
利用局部评估的分布式图模式匹配算法
3
作者 张丽霞 王伟平 +1 位作者 高建良 王建新 《国防科技大学学报》 EI CAS CSCD 北大核心 2016年第2期75-81,共7页
为了在分布式存储的大规模数据图上进行快速图模式匹配,提出利用局部评估的分布式图模式匹配算法。各计算节点并行地执行本地匹配;协调器节点收集局部匹配结果、计算边界点的匹配状态并发送给相应的计算节点;计算节点根据边界点的匹配... 为了在分布式存储的大规模数据图上进行快速图模式匹配,提出利用局部评估的分布式图模式匹配算法。各计算节点并行地执行本地匹配;协调器节点收集局部匹配结果、计算边界点的匹配状态并发送给相应的计算节点;计算节点根据边界点的匹配状态确定与边界点相连的节点的匹配情况;协调器节点组合得出最大匹配集。实验结果表明:与已有的分布式图模式匹配算法相比,dis GPM-PE算法都能够在不显著增加通信量的前提下避免数据片段间的依赖关系对执行时间的影响,从而减少图模式匹配的时间。 展开更多
关键词 图模式匹配 分布式算法 局部评估
下载PDF
一种基于图模式匹配的逻辑单元映射算法 被引量:4
4
作者 倪刚 来金梅 童家榕 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2006年第12期1850-1854,共5页
基于数学中图模式匹配的概念,根据电路特征在子图同构算法中加入图约束条件,研究了针对不同结构的FPGA逻辑单元都能适用的映射算法FDUMap·实验中应用FDUMap将测试电路映射到不同的逻辑单元中·该算法比现有的专用的逻辑单元映... 基于数学中图模式匹配的概念,根据电路特征在子图同构算法中加入图约束条件,研究了针对不同结构的FPGA逻辑单元都能适用的映射算法FDUMap·实验中应用FDUMap将测试电路映射到不同的逻辑单元中·该算法比现有的专用的逻辑单元映射算法通用性更好,而平均性能上仅相差3%· 展开更多
关键词 逻辑单元映射 工艺映射 图模式匹配 现场可编程门阵列
下载PDF
基于2-hop优化的子图模式匹配算法 被引量:1
5
作者 张航 王宏志 +1 位作者 李建中 高宏 《黑龙江大学自然科学学报》 CAS 北大核心 2010年第1期78-82,共5页
讨论大图上有效可达标记2-hop编码,及其构造的图结构信息数据结构在判定两点之间可达性的高效性,基于这些高效结构,提出一种基于栈的DAG全局图模式匹配算法,该算法结合了栈在匹配过程中线性空间开销的优势。实验结果表明,相对于目前主... 讨论大图上有效可达标记2-hop编码,及其构造的图结构信息数据结构在判定两点之间可达性的高效性,基于这些高效结构,提出一种基于栈的DAG全局图模式匹配算法,该算法结合了栈在匹配过程中线性空间开销的优势。实验结果表明,相对于目前主流的图模式匹配算法,该算法具有中间结果小,时间高效的优势。 展开更多
关键词 查询 2-hop编码 整体图模式匹配
下载PDF
图数据流上时间尊重图模式匹配算法研究 被引量:1
6
作者 侯晓双 张俊 《计算机应用研究》 CSCD 北大核心 2021年第7期1988-1992,共5页
现有的动态子图匹配研究中忽略了模式图中的时间信息,使用户难以得到想要查询的真实结果。针对这种情况,首先设计一种简洁的中间结果保存形式,将匹配结果直接在数据图中以图进行存储;接着改进边缘转换模型,当数据图有边插入/删除时对其... 现有的动态子图匹配研究中忽略了模式图中的时间信息,使用户难以得到想要查询的真实结果。针对这种情况,首先设计一种简洁的中间结果保存形式,将匹配结果直接在数据图中以图进行存储;接着改进边缘转换模型,当数据图有边插入/删除时对其快速增量维护并报告结果;最后根据边转换模型设计了一个时间尊重图模式匹配算法,提高了匹配搜索效率。对真实网络流量数据和综合社交流数据进行实验评估,结果表明算法能够有效减少图模式匹配的执行时间和空间花销。 展开更多
关键词 数据流 图模式匹配 时间尊重
下载PDF
基于结构分解的分布式RDF图模式匹配优化算法
7
作者 孙云浩 邢维康 +2 位作者 李冠宇 韩冰 李逢雨 《计算机应用与软件》 北大核心 2022年第6期228-238,共11页
在分布式RDF查询处理中,由于查询图规模的不断增长,其复杂的结构使得查询优化面临着查询准确性和性能的双重挑战。针对这一问题,提出一种由结构主导的分布式子图匹配算法SDSM。根据查询图各部分结构的匹配特征,提出查询图的CPM分解模型... 在分布式RDF查询处理中,由于查询图规模的不断增长,其复杂的结构使得查询优化面临着查询准确性和性能的双重挑战。针对这一问题,提出一种由结构主导的分布式子图匹配算法SDSM。根据查询图各部分结构的匹配特征,提出查询图的CPM分解模型;结合基于类型的摘要统计,通过代价模型得到查询起始节点及核心结构权重图,权重图与最小生成树思想相结合得到最优的查询匹配序列;各计算节点分两阶段进行查询,并在主机上进行轻量级的连接。实验将SDSM与StarMR、TriAD、Wukong等算法进行对比。结果表明,在处理复杂查询时,SDSM具有更高的查询效率,在多台机器以及不同数据集规模上的实验表明,SDSM也具有良好的扩展性。 展开更多
关键词 分布式 RDF图模式匹配 结构分解 以类型为中心的评估 查询处理
下载PDF
时态图上图模式匹配研究综述
8
作者 李发明 邹兆年 李建中 《智能计算机与应用》 2021年第8期189-192,F0003,共5页
图数据模型是一种通用且已经得到广泛应用的可以处理数据对象间复杂关系的数据模型。然而,现有的大多数研究只关注静态图数据的结构或者顶点和边上的属性,忽略了现实中数据的一个重要特征即时态信息。忽略了时态信息将导致错过很多的有... 图数据模型是一种通用且已经得到广泛应用的可以处理数据对象间复杂关系的数据模型。然而,现有的大多数研究只关注静态图数据的结构或者顶点和边上的属性,忽略了现实中数据的一个重要特征即时态信息。忽略了时态信息将导致错过很多的有价值的信息,甚至得到错误的信息。作为图研究领域中重要的研究内容之一,图模式匹配问题的研究也需要考虑时态信息。考虑到图模式匹配研究的重要性以及时态信息对数据的重要性,本文根据时态图的快照模型、边流模型和区间模型以及时态图数据的时序性、持续性和演化性对时态图上图模式匹配问题进行了全面地综述,并总结了现有工作的不足。 展开更多
关键词 时态信息 时态 图模式匹配
下载PDF
基于强社交图的多约束信任图模式增量匹配算法
9
作者 王钰蓉 丁鹏飞 刘安 《计算机应用与软件》 北大核心 2021年第8期248-258,314,共12页
针对现有的图匹配方法没有考虑到社交背景下的多种约束以及在多约束图匹配中图结构的变化,提出一种多约束图模式匹配方法。为了提高多约束图模式匹配的效率,提出强社交图的概念及一种强社交图的索引结构来索引图的可达性、图模式和上下... 针对现有的图匹配方法没有考虑到社交背景下的多种约束以及在多约束图匹配中图结构的变化,提出一种多约束图模式匹配方法。为了提高多约束图模式匹配的效率,提出强社交图的概念及一种强社交图的索引结构来索引图的可达性、图模式和上下文背景信息,提出维护强社交图索引的算法INC-SSG和多约束图匹配的增量算法SSG-IncMGPM,当面对强社交图结构的变化时能快速有效地识别多约束图模式匹配结果。通过对五个真实社交图的实证研究,验证了该方法在效率和有效性方面的优越性。 展开更多
关键词 多约束 信任 社交网络 图模式匹配
下载PDF
大规模图数据匹配技术综述 被引量:36
10
作者 于静 刘燕兵 +3 位作者 张宇 刘梦雅 谭建龙 郭莉 《计算机研究与发展》 EI CSCD 北大核心 2015年第2期391-409,共19页
在大数据时代海量的多源异构数据间存在着紧密的关联性,图作为表示数据之间关系的基本结构在社交网络分析、社会安全分析、生物数据分析等领域有着广泛应用.在大规模图数据上进行高效地查询、匹配是大数据分析处理的基础问题.从应用角... 在大数据时代海量的多源异构数据间存在着紧密的关联性,图作为表示数据之间关系的基本结构在社交网络分析、社会安全分析、生物数据分析等领域有着广泛应用.在大规模图数据上进行高效地查询、匹配是大数据分析处理的基础问题.从应用角度对用于图查询的图数据匹配技术的研究进展进行综述,根据图数据的不同特征以及应用的不同需求对图匹配问题分类进行介绍.同时,将重点介绍精确图匹配,包括无索引的匹配和基于索引的匹配,以及相关的关键技术、主要算法、性能评价等进行了介绍、测试和分析.最后对图匹配技术的应用现状和面临的问题进行了总结,并对该技术的未来发展趋势进行了展望. 展开更多
关键词 数据管理 图模式匹配 精确匹配 同构 索引技术 搜索
下载PDF
基于结构分解的动态图增量匹配算法 被引量:3
11
作者 许嘉 张千桢 +2 位作者 赵翔 吕品 李陶深 《计算机科学与探索》 CSCD 北大核心 2018年第8期1214-1224,共11页
在大数据时代,图数据的规模急剧增长,增量图模式匹配技术能够在数据图发生变化时避免重新对整个数据图进行匹配,进而减少匹配时间,提高整体执行效率,因此成为研究热点。然而,现有的增量匹配算法处理规模较大的模式图时效率会降低。针对... 在大数据时代,图数据的规模急剧增长,增量图模式匹配技术能够在数据图发生变化时避免重新对整个数据图进行匹配,进而减少匹配时间,提高整体执行效率,因此成为研究热点。然而,现有的增量匹配算法处理规模较大的模式图时效率会降低。针对该问题,提出了一种基于结构分解的增量图模式匹配算法Inc_CFLS。在匹配过程中,为中间匹配结果构建高效索引,用于后续的模式匹配计算。基于构建的索引信息对数据图增加边事件进行分类,进而为每类增加边事件设计查询剪枝优化策略,从而有效提高匹配效率。在真实数据集上进行实验,结果表明Inc_CFLS算法比目前最好的增量匹配算法在执行效率上平均提升了1~2倍,能更有效支持大规模动态图上的模式匹配。 展开更多
关键词 动态 图模式匹配 增量算法 结构分解 数据
下载PDF
大规模数据图上的个性化子图匹配算法 被引量:5
12
作者 杨艳 纪安娜 金虎 《计算机研究与发展》 EI CSCD 北大核心 2015年第S1期48-55,共8页
以图结构来描述实体间复杂的关联关系被广泛应用于多种不同的领域.但是,随着这些领域的蓬勃发展,图结构数据的数据量也与日俱增.如何根据用户提交的查询图,在大规模数据图上高效地返回满足用户要求的匹配成为目前学术界和工业界首要的... 以图结构来描述实体间复杂的关联关系被广泛应用于多种不同的领域.但是,随着这些领域的蓬勃发展,图结构数据的数据量也与日俱增.如何根据用户提交的查询图,在大规模数据图上高效地返回满足用户要求的匹配成为目前学术界和工业界首要的研究问题.然而,之前的工作,多数都是在无权图上查询,没有考虑用户的个性化需求,并且算法运行在大规模数据图上的执行时间并不是很理想.提出一个适用于有权查询图并且适用于大规模数据图上查询的个性化子图匹配算法(personalized subgraph matching,PSM).首先,通过已有的社团检测GN算法将数据图划分成若干个子区域,并构建2个线下索引:GP-Tree索引和排序边集索引(sorted lists index,SL);然后,基于索引结构,通过增加优化策略进而加速子图匹配;最后,本文通过大量实验验证了本文算法的有效性和扩展性. 展开更多
关键词 匹配 数据 图模式匹配 分割 索引技术
下载PDF
强模拟在带权有向图的扩展及其匹配结果的排序 被引量:1
13
作者 沈嘉思 《现代电信科技》 2012年第9期53-57,共5页
图模式匹配是互联网海量数据库应用的关键技术。强模拟是现在一种实际应用效果较好的图模式匹配模型,但它无法对匹配结果按照重要程度排序。本文将强模拟推广到了带权有向图中,使用边的权值衡量和比较不同匹配子图或子图内部不同顶点的... 图模式匹配是互联网海量数据库应用的关键技术。强模拟是现在一种实际应用效果较好的图模式匹配模型,但它无法对匹配结果按照重要程度排序。本文将强模拟推广到了带权有向图中,使用边的权值衡量和比较不同匹配子图或子图内部不同顶点的重要性,对匹配结果进行排序。 展开更多
关键词 图模式匹配 强模拟 排序 带权有向
下载PDF
大规模RDF图数据上高效率分布式查询处理 被引量:9
14
作者 王鑫 徐强 +2 位作者 柴乐乐 杨雅君 柴云鹏 《软件学报》 EI CSCD 北大核心 2019年第3期498-514,共17页
知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框架(resourcedescriptionframework,简称RDF)形式发布出来.RDF图上的SPARQL查询语义对应于图同态,是一个NP-完全问题.因此,如何使用分布式方... 知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框架(resourcedescriptionframework,简称RDF)形式发布出来.RDF图上的SPARQL查询语义对应于图同态,是一个NP-完全问题.因此,如何使用分布式方法在大规模RDF图上有效回答SPARQL查询是一个富有挑战性的问题.目前已有研究使用MapReduce计算模型处理大规模RDF数据,但其将SPARQL查询拆分成单个的查询子句,没有考虑RDF数据的丰富语义和自身的图特性,导致Map Reduce迭代次数过多.首先,利用RDF数据内嵌的语义和结构信息作为启发式信息,将查询图分解为星形的集合,可以在更少次迭代内得到查询结果.同时,分解算法给出中间结果较少的星形匹配顺序,基于此顺序,每轮Map Reduce操作通过连接操作匹配一个新的星形,直至产生最终的答案.最后,在标准合成数据集WatDiv和真实数据集DBpedia上进行大量的实验评估.实验结果表明:所提基于星形分解的分布式SPARQLBGP匹配算法能够高效回答查询,查询时间比SHARD和S2X算法的查询时间平均提高一个数量级,且优化算法的查询时间与基本算法相比缩短了49.63%~78.71%. 展开更多
关键词 星形分解 分布式 基本图模式匹配 大规模RDF MAPREDUCE
下载PDF
面向大图数据的并行图查询
15
作者 刘小轩 《现代电子技术》 北大核心 2019年第20期45-47,52,共4页
针对传统图模式查询算法难以实现在大图数据上查询或查询时间太长问题,提出基于MapReduce的图查询并行算法PGPQ。该方法包括计算初始匹配节点集、初始不匹配父亲节点集和图模式查询三个部分。在图模式查询过程利用初始不匹配父亲节点集... 针对传统图模式查询算法难以实现在大图数据上查询或查询时间太长问题,提出基于MapReduce的图查询并行算法PGPQ。该方法包括计算初始匹配节点集、初始不匹配父亲节点集和图模式查询三个部分。在图模式查询过程利用初始不匹配父亲节点集迭代初始匹配节点集中的节点,如果数据图匹配模式图,返回一个最大的匹配。实验结果表明,PGPQ算法查询能有效地进行大图模式查询。 展开更多
关键词 并行处理 模式查询 图模式匹配 数据 MAPREDUCE 实验验证
下载PDF
基于关联分析的铁路旅客同行预测方法 被引量:1
16
作者 李思颖 徐杨 +1 位作者 王欣 赵若成 《计算机科学》 CSCD 北大核心 2021年第9期95-102,共8页
随着运输技术的快速发展,铁路已成为人们出差、度假、探亲时选择的主要出行方式之一。与此同时,旅客共同出行(以下简称同行)的行为特征也越来越普遍。依据旅客间的同行关系,可以构建同行关系网络;而对该网络中潜在的链接进行预测,将有... 随着运输技术的快速发展,铁路已成为人们出差、度假、探亲时选择的主要出行方式之一。与此同时,旅客共同出行(以下简称同行)的行为特征也越来越普遍。依据旅客间的同行关系,可以构建同行关系网络;而对该网络中潜在的链接进行预测,将有助于提供个性化的服务和产品。为此,文中提出一种原创的方法,用于在旅客同行关系网络中发现潜在的同行关系。首先对传统的图模式关联规则进行扩展,提出了两类“同行图模式关联规则”,用于预测新的同行关系和未来的同行频次。然后,将上述规则挖掘计算的问题分解为频繁同行模式挖掘、规则生成以及关联分析3个子问题,并设计了有效的分布式和集中式的算法。通过在大规模真实数据集上的测试,证明了所提方法能够高效且准确地预测旅客同行关系网络中潜在的同行关系,且两类规则的预测准确率均高于50%,远高于传统方法(如Jaccard的预测准确率为24%)。 展开更多
关键词 同行预测 同行网络 关联分析 图模式匹配 同行模式
下载PDF
A color based face detection system using multiple templates 被引量:1
17
作者 王涛 卜佳酸 陈纯 《Journal of Zhejiang University Science》 CSCD 2003年第2期162-165,共4页
A color based system using multiple templates was developed and implem ented for detecting human faces in color images. The algorithm consists of three image processing steps. The first step is human skin color stati... A color based system using multiple templates was developed and implem ented for detecting human faces in color images. The algorithm consists of three image processing steps. The first step is human skin color statistics. Then it separates skin regions from non-skin regions. After that, it locates the fronta l human face(s) within the skin regions. In the first step, 250 skin samples from persons of different ethnicities are used to determine the color distribution o f human skin in chromatic color space in order to get a chroma chart showing lik elihoods of skin colors. This chroma chart is used to generate, from the origina l color image, a gray scale image whose gray value at a pixel shows its likelih ood of representing the skin. The algorithm uses an adaptive thresholding proces s to achieve the optimal threshold value for dividing the gray scale image into separate skin regions from non skin regions. Finally, multiple face templates ma tching is used to determine if a given skin region represents a frontal human fa ce or not. Test of the system with more than 400 color images showed that the re sulting detection rate was 83%, which is better than most color-based face dete c tion systems. The average speed for face detection is 0.8 second/image (400×300 pixels) on a Pentium 3 (800MHz) PC. 展开更多
关键词 Color-based Multiple templates matching Face detecti on
下载PDF
通用的FPGA逻辑单元映射工具 被引量:1
18
作者 倪刚 童家榕 来金梅 《复旦学报(自然科学版)》 CAS CSCD 北大核心 2006年第4期533-537,541,共6页
提出了基于图模式匹配的逻辑单元映射的新颖思想,开发了针对不同结构的逻辑单元都能适用的映射工具FDUMap.实验中应用FDUMap将测试电路映射到不同的逻辑单元中,该工具比起现有的几种专用的逻辑单元映射工具,有更好的通用性.
关键词 逻辑单元映射 工艺映射 图模式匹配 现场可编程门阵列
下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部