检索结果-南通市图书馆

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

动态图模式匹配技术综述

软件学报 2018年第3期29卷 663-688页

作者：许嘉张千桢赵翔吕品李陶深广西大学计算机与电子信息学院广西南宁530004 广西高校并行分布式计算技术重点实验室(广西大学) 广西南宁530004 广西高校多媒体通信与信息处理重点实验室(广西大学) 广西南宁530004 国防科技大学系统工程学院湖南长沙410073

随着大数据时代的到来,多源异构数据的快速增长已经成为开放性问题,数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中,例如网络安全分析和社交网络舆情分析,描述实体对象之间关系的图数据的结构和内容往往不是固定不变... 详细信息

随着大数据时代的到来,多源异构数据的快速增长已经成为开放性问题,数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中,例如网络安全分析和社交网络舆情分析,描述实体对象之间关系的图数据的结构和内容往往不是固定不变的,图数据的结构以及节点和边的属性会随着时间的推移发生更新变化.因此,如何在动态更新的图数据中进行高效的查询、匹配,是目前研究的热点问题.从关键技术、代表性算法和性能评价方面概述动态图模式匹配技术的研究进展.最后,对动态图模式匹配技术的典型应用、面临的挑战问题和未来发展趋势进行了总结和展望.

关键词：动态图图模式匹配子图同构匹配算法图搜索

在线全文

学校读者我要写书评

暂无评论

面向模式图变化的增量图模式匹配

软件学报 2015年第11期26卷 2964-2980页

作者：张丽霞王伟平高建良王建新中南大学信息科学与工程学院湖南长沙410083 湖南师范大学数学与计算机科学学院湖南长沙410081

在大数据时代,数据图的规模急剧增长,增量图模式匹配算法能够在数据图或模式图发生变化时避免重新在整个数据图上进行匹配、减少响应时间,因此成为了研究的热点.针对实际应用中数据图不变而模式图发生变化的情况,提出了一种面向模式图... 详细信息

在大数据时代,数据图的规模急剧增长,增量图模式匹配算法能够在数据图或模式图发生变化时避免重新在整个数据图上进行匹配、减少响应时间,因此成为了研究的热点.针对实际应用中数据图不变而模式图发生变化的情况,提出了一种面向模式图变化的增量图模式匹配算法PGC_Inc GPM,在模式图匹配的过程中记录适当的中间结果作为索引,用于后续的模式匹配.提出了增强的图模式匹配算法GPMS,用于首次整个数据图上的模式匹配.该算法一方面能够建立后续增量匹配所需的索引,另一方面减少了整个数据图匹配的执行时间.设计实现了面向模式图增边和减边的两个核心子算法,通过子算法的组合,能够支持在模式图发生各种变化时进行增量图模式匹配.在真实数据集和合成数据集上进行实验,结果表明:与重新在整个数据图上进行匹配的Re Computing算法相比,当模式图中变化的边的数目不超过不变的边的数目时,PGC_Inc GPM算法能够有效减少图模式匹配的执行时间;随着数据图规模的增大,PGC_Inc GPM算法相对于Re Computing算法的执行时间的减少程度更加明显,对于大规模数据图具有更好的适用性.

关键词：图模式匹配增量算法动态图大数据

在线全文

学校读者我要写书评

暂无评论

利用局部评估的分布式图模式匹配算法

国防科技大学学报 2016年第2期38卷 75-81页

作者：张丽霞王伟平高建良王建新中南大学信息科学与工程学院湖南长沙410083 湖南师范大学数学与计算机学院湖南长沙410081

为了在分布式存储的大规模数据图上进行快速图模式匹配,提出利用局部评估的分布式图模式匹配算法。各计算节点并行地执行本地匹配;协调器节点收集局部匹配结果、计算边界点的匹配状态并发送给相应的计算节点;计算节点根据边界点的匹配... 详细信息

为了在分布式存储的大规模数据图上进行快速图模式匹配,提出利用局部评估的分布式图模式匹配算法。各计算节点并行地执行本地匹配;协调器节点收集局部匹配结果、计算边界点的匹配状态并发送给相应的计算节点;计算节点根据边界点的匹配状态确定与边界点相连的节点的匹配情况;协调器节点组合得出最大匹配集。实验结果表明:与已有的分布式图模式匹配算法相比,dis GPM-PE算法都能够在不显著增加通信量的前提下避免数据片段间的依赖关系对执行时间的影响,从而减少图模式匹配的时间。

关键词：图模式匹配分布式算法局部评估

在线全文

学校读者我要写书评

暂无评论

一种基于图模式匹配的逻辑单元映射算法

计算机辅助设计与图形学学报 2006年第12期18卷 1850-1854页

作者：倪刚来金梅童家榕复旦大学专用集成电路与系统国家重点实验室上海201203

基于数学中图模式匹配的概念,根据电路特征在子图同构算法中加入图约束条件,研究了针对不同结构的FPGA逻辑单元都能适用的映射算法FDUMap·实验中应用FDUMap将测试电路映射到不同的逻辑单元中·该算法比现有的专用的逻辑单元映射算法通... 详细信息

基于数学中图模式匹配的概念,根据电路特征在子图同构算法中加入图约束条件,研究了针对不同结构的FPGA逻辑单元都能适用的映射算法FDUMap·实验中应用FDUMap将测试电路映射到不同的逻辑单元中·该算法比现有的专用的逻辑单元映射算法通用性更好,而平均性能上仅相差3%·

关键词：逻辑单元映射工艺映射图模式匹配现场可编程门阵列

在线全文

学校读者我要写书评

暂无评论

面向群体需求场景的多约束图模式匹配研究

面向群体需求场景的多约束图模式匹配研究

作者：赵海霞合肥工业大学

学位级别：硕士

复杂社交网络(CSG)因其蕴含丰富上下文信息已经成为众多学者的研究对象。通过设计含多属性需求的模式图,图模式匹配得以有效利用该丰富信息因而在CSG领域得到广泛应用。然而,随着决策问题日益复杂、决策者(Decision Makers,DMs)数量增多... 详细信息

复杂社交网络(CSG)因其蕴含丰富上下文信息已经成为众多学者的研究对象。通过设计含多属性需求的模式图,图模式匹配得以有效利用该丰富信息因而在CSG领域得到广泛应用。然而,随着决策问题日益复杂、决策者(Decision Makers,DMs)数量增多,模式图复杂性也不断增加:不同决策者对模式图中各属性常有不同需求。因而如何聚合各需求得到满足决策者偏好的模式图为多约束图模式匹配问题带来了新挑战。本文旨在研究在群体需求场景下如何聚合节点及边属性约束、合理设置模式图中路径约束,从而进行有效子图匹配返回符合DMs偏好的子图。提升匹配速度同时进一步提高匹配结果准确性。以下是研究的具体内容:(1)针对已有多约束图模式匹配方法中属性约束多源于单决策者,导致难以适应群体需求应用情景的问题,提出一个基于多属性需求聚合的子图查询模型MR-SQ。该模型引入直觉模糊理论和二项式加权求和思想,提出IFRA方法对多决策者边/节点属性需求进行归一并聚合,实现对模式图的属性约束设置;在模型的图模式匹配阶段,引入并行策略达到缩短大图中查询时间的目的。在数据集上进行的算例实验、扰动实验、对比实验,其结果验证了 MR-SQ模型在大图匹配中的可行性和稳定性,以及模式图约束设置对匹配质量提升的有效性。(2)针对已有方法对模式图中有界路径长度约束多采用随机策略,难以为决策者提供路径约束参考的问题,提出了多约束图匹配中有界路径长度约束设计算法MCTS-MCSP。首先,分析通过多约束最短路径查询设置路径长度约束的可行性。其次,在强化学习思想下,提出一种基于蒙特卡洛树搜索的多约束路径查询方法。该方法将路径查询任务转化为马尔可夫决策过程,采用蒙特卡洛树搜索进行最短路径查询。通过实验,验证了所提算法在大图中路径查找的高效性,以及预先进行最短路径查询对决策者约束设置的有益性、对提升匹配结果精度及平衡查询时间的效用性。

关键词：图模式匹配复杂社交网络直觉模糊集最短路径查询蒙特卡洛树搜索

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

含有计数量词的图模式匹配研究与实现

含有计数量词的图模式匹配研究与实现

作者：何春贤哈尔滨工业大学

学位级别：硕士

计数量词作为一种增强表达的方式,加入到图模式匹配中可以更加准确地描述客观世界。通过简单地在查询图的边上附加计数量词可以很自然的表达出全部和存在量化表达,比例和数量聚集表达,以及否定表达。这种增加了表达能力的图模式匹配在... 详细信息

计数量词作为一种增强表达的方式,加入到图模式匹配中可以更加准确地描述客观世界。通过简单地在查询图的边上附加计数量词可以很自然的表达出全部和存在量化表达,比例和数量聚集表达,以及否定表达。这种增加了表达能力的图模式匹配在社会媒体营销,知识发现,网络安全等领域都有广泛且直接的应用。关于量词化的图模式匹配问题的研究目前仍然比较新,而且该问题本身泛化了传统图模式匹配问题条件,传统图模式匹配问题仅属于本文问题的一个特例。因而本文所研究的量词化的图模式匹配问题复杂度远难于传统的图模式匹配。用边上计数量词是否包含否定计数量词可以将该问题划分成两个复杂度相异的两个子问题,第一类子问题模式图边上只包含肯定的计数量词,它的复杂度可以证明是NP完全的,并且在特定条件下复杂度的上下界都为NP难,而含有否定计数量词边的匹配问题复杂度则是DP完全的,特定条件下复杂度上下界为DP难,如此高的复杂度使得蛮力法解决该问题的开销无法令人接受。本文实现了(1)正QGP问题的匹配算法QMatch,该算法通过调用子图同构子算法而改进实现,本文通过实验验证发现算法在模式图规模在4以内时的匹配时间是比较好的,规模变大后的匹配时间呈指数式增长。(2)负QGP问题的匹配算法Inc QMatch,该算法避免了直接验证负计数量词的高复杂度,在正问题解决的基础上,利用集差思想,构建两个新的查询图结构得到最后的结果集,通过记录终结结果集的方式可以避免第二次查询从头开始有效地减少了运行时间,并且通过多线程的方式对该问题的匹配实现了并行化,实验表明当边上的负计数量词个数只有一时,Inc QMatch的时间开销在查询图规模超过4以后同样呈显指数式的增长。(3)利用哈希编码技术给节点周围边标签和节点标签进行编码,通过与的手段压缩周围结构信息,并将周围的标签种类信息压缩到一串二进制字串当中,通过或运算匹配节点,得到小规模候选集合,在本文实验中,使用8+8位编码,可以过滤掉95%的不匹配,优化效率非常明显,且在查询图规模是6的时候都表现出了小于10秒的运行时间,优化效果非常显著。

关键词：计数量词图模式匹配子图同构哈希签名

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于亲属关系网络的图模式匹配方法研究

基于亲属关系网络的图模式匹配方法研究

作者：张浩河北师范大学

学位级别：硕士

亲属关系网络描述了人与人之间的血缘、婚姻关系,随着数据规模的提升以及人与人之间关系复杂性的提高,如何在亲属关系网络中匹配特定模式的亲属关系结构成为研究难点之一。关系数据库在支持复杂关系查询上已难以满足要求,相比之下图数... 详细信息

亲属关系网络描述了人与人之间的血缘、婚姻关系,随着数据规模的提升以及人与人之间关系复杂性的提高,如何在亲属关系网络中匹配特定模式的亲属关系结构成为研究难点之一。关系数据库在支持复杂关系查询上已难以满足要求,相比之下图数据库针对大量结构复杂数据的存储和查询上具有明显优势。在亲属关系网络的查询中,以家庭成员组成的结构搜索是典型的图模式匹配问题。由于子图同构方法匹配描述缺少针对模式图的限制语义,在亲属关系网络中,无法依据个性化的需求匹配特定模式的图结构。本文以图数据模型对真实亲属关系网络建模,在存储方法和查询效率上分别与关系模型进行对比。针对亲属关系结构查询问题,提出限制图模式匹配方法,在查询模式图中加入对于节点和边的限制语义,丰富模式图语义描述。将限制图模式匹配方法应用到亲属关系网络中,依据人口学中家庭结构的分类标准对亲属关系家庭结构进行匹配,并对匹配结果进行分析和可视化展示。本文具体研究内容主要包含以下几方面:(1)以图模式存储亲属关系网络。亲属关系网络结构复杂,人与人之间的复杂亲属关系查询对数据底层组织要求较高。本文以H省真实亲属关系网络数据为基础,结合亲属关系网络数据的语义和数据规模,以属性图(Property graph)数据结构描述亲属关系网络。分析亲属关系网络的关系模型建模方法,以图模型针对亲属网络数据建模并实现关系模型到图模型的数据存储转换。实验对比两种存储模式中复杂关系的查询方法,随着查询深度的增加,相对关系模型下表之间连接的复杂性,图模型下基于图模式的查询方式更简洁高效。(2)提出了限制图模式匹配方法。在亲属关系网络中,以家庭成员组成结构为条件的搜索是典型的图模式匹配问题。在亲属关系网络的特定亲属关系结构查找中,查询模式图的语义表述尤为重要。本文利用子图同构方法对亲属关系网络进行查询,发现查询模式图在语义表述上缺少限制语义描述,提出限制图模式匹配定义和匹配规则描述,为模式图增加节点和边的数目、类型限制语义,并对限制模式匹配规则进行了具体阐述,丰富查询图的语义信息以实现特殊结构匹配,并通过实验验证了限制图模式匹配方法的有效性和查询结果的正确性。(3)实验对比关系数据库与图数据库查询性能。以H省亲属关系网络为实验数据,分别实现关系模式的存储和图模式存储。在两种存储模式下,针对相同规模亲属关系网络数据,以相同查询目标进行查询方法的比对以及查询效率的评估。实验结果表明,以图模式存储的数据查询效率优于关系数据库。(4)将限制图模式匹配应用于亲属关系网络的家庭结构查询。为了实现家庭结构的模式匹配,扩展亲属关系网络,添加家庭户节点以及人与户之间的关系边,利用人口学中家庭分类的标准,分别对核心家庭、直系家庭、单亲家庭构建相应的模式图,根据限制模式图匹配规则,在亲属关系网络匹配中进行查询,并对结果的准确性进行评估。

关键词：亲属关系网络图模式匹配图数据库限制模式图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于正则表达式的图模式匹配算法研究

基于正则表达式的图模式匹配算法研究

作者：薛少童河北师范大学

学位级别：硕士

Web2.0时代下,人与人之间通过社交网络进行交互连接,以社交网络的网络结构为单位传播信息。社交网络的网络结构是指网络中成员的构成及其相互作用、相互影响的状态,以及由这种状态形成的相对稳定的联系模式。随着社交网络的应用逐渐广... 详细信息

Web2.0时代下,人与人之间通过社交网络进行交互连接,以社交网络的网络结构为单位传播信息。社交网络的网络结构是指网络中成员的构成及其相互作用、相互影响的状态,以及由这种状态形成的相对稳定的联系模式。随着社交网络的应用逐渐广泛与流行,网络中成员间关系的复杂性呈指数增长。其关系复杂性的增加,一方面加剧了网络数据的挖掘难度,另一方面大幅提高了社交网络中复杂关系的研究价值。本文基于图数据库存储模式,深入分析社交网络的网络结构,以网络中的成员为节点,成员之间不同类型的连接为指向关系边,构造基于正则表达式的匹配模型,给出相应的算法并成功应用于人口研究领域,实现高效新型的家庭分类的统计查询。在理论研究的基础上为人口大数据的研究开创了新的思路。本文主要完成了以下几个方面的工作:1)基于正则表达式构造匹配模型。在分析图数据库中存储的Essembly社交网络数据基础上,结合正则表达式的匹配描述,给出数据图和模式图的定义。进而从节点间的结构信息与节点属性以及节点间指向关系边的语义信息出发,构造概念匹配模型。并以真实家庭结构的人口数据建立对应的应用模型。2)提出基于正则表达式的图模式匹配算法。基于强模拟算法思想,采用正则表达式匹配引擎构造的匹配模型,应用近似最优解代替最优解的近似图匹配方法,在大规模社交网络数据图中,提出基于正则表达式的图模式匹配算法,对社交网络的网络结构进行查询。3)使用不同数据集验证算法的可行性。文章选用三个不同数据集,从节点属性、标签以及边类别等方面比较实验数据。从准确率和效率两个方面,对提出的基于正则表达式的图模式匹配算法的可行性,进行实验验证。其中,效率方面,在相同规模查询模式图中,将算法基于三个数据集的查询时间进行对比;准确率方面,选取市级人口数据,以夫妇核心家庭为例进行查询,统计家庭户内人口比例以及家庭户比例,并将算法查询结果与人口研究领域中入户统计结果进行对比。4)将算法应用于人口领域,进行家庭分类查询。基于H省全员人口数据库,发现隐含人口亲属关系,构建亲属关系网络。基于亲属关系网络,以核心家庭为例,分析发现家庭结构中的人口数与关系边数、家庭模式数均具有一定数量关系,同类别的家庭结构存在特定的家庭模式。使用本文提出的算法,以核心家庭、一代核心家庭、二代核心家庭为例,进行家庭分类查询。查询结果显示,家庭结构逐渐趋于小型化,核心家庭已成为家庭中的主力军。

关键词：社交网络网络结构正则表达式图模式匹配家庭分类查询

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向大图数据的图模式匹配研究

面向大图数据的图模式匹配研究

作者：张芳合肥工业大学

学位级别：硕士

大图,特别是社交网络,吸引了越来越多的学者关注,其中最重要的研究领域之一是图模式匹配,尤其是大图数据中的图模式匹配。利用图模式匹配,我们可以设计满足特殊个性化需求的模式图,并找到符合所需模式的子图。那么如何在特定领域有效地... 详细信息

大图,特别是社交网络,吸引了越来越多的学者关注,其中最重要的研究领域之一是图模式匹配,尤其是大图数据中的图模式匹配。利用图模式匹配,我们可以设计满足特殊个性化需求的模式图,并找到符合所需模式的子图。那么如何在特定领域有效地在大图中找到具有更好属性的图模式成为分析和处理大图数据的关键问题。为了在大图数据中快速的找到匹配子图以及在匹配子图集中快速的找到较优的匹配子图,本文提出一种新颖的基于可靠性的多模糊目标图模式匹配方法。本文的主要工作如下:(1)针对现有的网络多标签分类工作中,虽然只需要确定某些未知节点的标签,但必须推断出网络中所有节点的标签的情况,本文提出由已知标签信息的节点和目标标签节点以及它们之间的最短路径构成的多目标核心网络。(2)针对传统的多约束图模式匹配中用精确的数值判断社交的信任程度带有主观意识性以及选择更多更好的匹配子图的情况,本文引入了模糊数,提出一种多模糊目标图模式匹配方法,实验结果证明我们提出的方法可以选择更多更好的匹配子图。(3)针对传统的多约束图模式匹配中匹配子图中的某个节点可能出现故障的情况,本文引入可靠性的理论来评估一个匹配子图的可靠性,提出一种基于可靠性的多模糊目标图模式匹配方法,实验结果证明我们提出算法的有效性。(4)针对如何从众多的匹配子图中找出多个目标都是较优的匹配子图的问题,本文引入了多目标优化算法。

关键词：多目标模糊可靠性图模式匹配大图数据