图数据库中的相似性搜索算法研究与应用*

图数据库的相似性搜索是一个非常重要的研究内容,图的相似性匹配属于图同构的判定问题,是NP完全问题,传统的高开销搜索的方法已经不能满足复杂图查询的需要;另外,由于图数据库的复杂性和特殊性,已有的优化算法不能直接使用。为了提高图数据库的搜索效率,提出了一种基于索引的相似性搜索算法,通过数据库中的频繁结构建立特征索引,算法可高效准确地滤除大量的非相似图集合,避免了图之间精确匹配即图同构的计算,最后将本算法应用于化学数据库,实验结果证明了该方法的有效性和可行性。     

基于FSG的最大频繁子图挖掘算法*

图挖掘已成为数据挖掘领域研究的热点,然而挖掘全部频繁子图很困难且得到的频繁子图过多,影响结果的理解和应用。可通过挖掘最大频繁子图来解决挖掘结果数量巨大的问题,最大频繁子图挖掘得到的结果数量很少且不丢失信息,节省了空间和以后的分析工作。基于算法FSG提出了最大频繁子图挖掘算法FSG-MaxGraph;结合节点的度、标记及邻接列表来计算规范编码,提出两个定理来减少子图同构判断的次数,并应用改进后的决策树来计算支持度。实验证明,新算法解决了挖掘结果太多理解困难的问题,且提高了挖掘效率。     

融合制造语义的三维工序模型序列重用方法

针对目前三维工序模型序列重用缺少对加工特征尺寸、加工精度、形位公差等制造信息的考虑,不能很好地支持零件制造过程工艺设计重用的问题,提出一种融合制造信息的三维工序模型序列重用方法.首先,利用图同构原理对工艺路线中三维工序模型序列进行优化,减少搜索空间;然后,利用子图同构对三维工序模型加工特征进行匹配,通过融合制造信息对加工特征匹配进行预处理和相似性评价,以获取具有最相似加工特征的三维工序模型;其次,设计三维工序模型序列优化算法获取同构的三维工序模型序列;最后,以某型轴零件工艺设计过程为例进行实例验证,结果表明融合制造信息的三维工序模型序列重用方法能够准确地根据指定制造特征进行工艺设计重用,具有良好的应用效果.     

采用图同构判定的工厂设计模型数据匹配研究

对工厂设计中的P&ID和配管设计图,提出模型拓扑图的映射规则,采用关联度序列法对拓扑图同构进行判定.映射规则将图论理论和工程实际相结合,实现了对两个模型拓扑图的简化.关联度序列法着眼于拓扑图中节点与边的匹配,同时兼顾拓扑关系匹配和工程数据匹配.实践证明,所提方法能够完成工厂设计模型的数据匹配,并能判断出不匹配的连通子图.     

基于子图同构的子电路提取算法

从门级到功能模块级的子电路提取问题在大规模集成电路计算机辅助设计领域有广泛地应用,提出了基于子图同构的方法来解决该问题。针对子电路的特征,选择辐射路匹配和赋标号算法之一作为搜索的主算法。尽管子图同构问题是NP完全问题,算法对实际的电路是快速的,满足工程需要。     

一个自授权系统及问题的知识复杂性*

基于图同构零知识证明的标识-鉴别-签名系统,提出了一个解决自授权问题的方法.与以前的方法相比,虽然两者都是基于对主秘密的逐步暴露来实现的,但前者是基于图同构置换来实现的,而后者是基于类似于秘密共享的思想来实现的.在研究给出的自授权系统的安全性时,定义了问题级的知识复杂性、实际知识复杂性和计算知识复杂性.应把它们作为协议知识复杂性的上界.     

大型模型克隆检测技术研究

模型克隆检测在软件维护、软件结构优化等方面具有重要价值和意义。首先综述了模型克隆的定义,接着对模型克隆的完整检测过程进行了详细划分和讨论,然后介绍了当前国际上最具代表性的两类大型模型克隆检测技术,最后对模型克隆检测的研究现状和亟需解决的问题进行了分析,并展望了该领域未来的研究方向。     

基于确定图的频繁子图挖掘技术概述

化学信息学、生物信息学、医学和社会科学等领域的科学研究的迅速发展积累了大量的图数据,如何从复杂和庞大的图数据中挖掘出有效信息成为数据挖掘领域的热点。通过介绍现阶段图数据挖掘技术的进展,特别是确定图挖掘技术中有代表性的频繁子图挖掘技术研究,讨论并预测了频繁子图挖掘研究的发展趋势。     

最大频繁子图挖掘算法研究

随着图的广泛应用,图的规模不断扩大,因此提高频繁子图挖掘效率势在必行。本文针对频繁子图挖掘所产生的庞大的结果集,提出了一个最大频繁子图挖掘算法MFME,从而极大地减少了结果集的数量。MFME使用了映射的思想将图集中的边映射到边表中并在此表上进行子图挖掘,有效地提高了算法的效率。实验结果表明,MFME的效率较经典算法SPIN有明显提高。     

动态图模式匹配技术综述

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